凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

PTA20+逻辑思维_给定n(n≤100)个正整数,所有正整数均≤1000000;求其中所有素数的和。

作者：凡人多烦事01 | 2024-03-28 08:17:26

踩

给定n(n≤100)个正整数,所有正整数均≤1000000;求其中所有素数的和。

1、打印沙漏

“沙漏形状”，是指每行输出奇数个符号；各行符号中心对齐；相邻两行符号数差2；符号数先从大到小顺序递减到1，再从小到大顺序递增；首尾符号数相等。给定任意N个符号，不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可能多的符号。
在这里插入图片描述

思路：奇数等差数列求和【首项1，尾项2i-1，共i项】=i * i ，则求n>=2 * i*i-1

int main(){
    int n,t,num;
    string in;
    //n >= 2*t*t-1，使用等差数列求和公式
    while (cin>>n>>in){
        t = int(sqrt((n+1)/2));
        num = 2*t-1;
        //打印倒三角
        for (int i=0;i<t;i++){
            for (int j=0;j<i;j++) cout<<" ";
            for (int j=i;j<num-i;j++) cout<<in;
            cout<<endl;
        }
        //打印正三角
        for (int i=t-2;i>-1;i--){
            for (int j=0;j<i;j++) cout<<" ";
            for (int j=i;j<num-i;j++) cout<<in;
            cout<<endl;
        }
        //求没用到的符号个数
        cout<<n-2*t*t+1;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2、猜数字

每人猜一个 100 以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。
【输入样例】
7
Bob 35
Amy 28
James 98
Alice 11
Jack 45
Smith 33
Chris 62
【输出样例】
22 Amy

思路：求平均值的一半，遍历求误差最小的人。排序+二分法超时了TAT

struct node{
    string name;
    int num;
};
bool cmp(node a,node b){return a.num<b.num;}
int main(){
    int n,sum=0;
    cin>>n;
    node info[n+1];
    for (int i=0;i<n;i++){
        cin>>info[i].name>>info[i].num;
        sum+=info[i].num;
    }
    int avg = sum/(n*2),maxi=0;
    for (int i=1;i<n;i++){
        if (abs(info[i].num-avg)<abs(info[maxi].num-avg)) maxi=i;
    }
    cout<<avg<<" "<<info[maxi].name;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、前世档案 y 代表“是”，用 n 代表“否”

在这里插入图片描述【输入样例】
3 4
yny
nyy
nyn
yyn
【输出样例】
3
5
6
2

思路：将y=0,n=1，将其二进制编码+1即为结果对应值

int main(){
    int n,m,res,t;
    cin>>n>>m;
    string in;
    while (m--){
        cin>>in;
        res=0;
        t=1;
        //二进制表示
        for (int i=n-1;i>-1;i--){
            if (in[i]=='n') res+=t;
            t *= 2;
        }
        cout<<res+1<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4、刮刮彩票

每次玩家拿到一张彩票，上面有 1 到 9 九个数字，并以 3×3 的“九宫格”形式排列。游戏开始时只能看见一个位置上的数字，可以再选择三个位置的数字刮开。最后再从 3 横、3 竖、2 斜共 8 个方向中挑选一个方向，方向上三个数字和可根据下列表格进行兑奖，获得对应数额的金币。
在这里插入图片描述
【输入样例】
1 2 3
4 5 6
7 8 0
1 1
2 2
2 3
7
【输出样例】
1
5
6
180

思路：对于寻找被刮的数字，采用和固定为45，减去已知数字的方法。

int main(){
    int sum=45,x,y,t,info[4][4],res[19]={10000,36,720,360,80,252,108,72,54,180,72,180,119,36,306,1080,144,1800,3600};
    for (int i=1;i<4;i++){
        for (int j=1;j<4;j++){
            cin>>info[i][j];
            if (info[i][j]==0){ //记住被刮开的数字
                x=i;
                y=j;
            }
            sum -= info[i][j]; //最后剩下几
        }
    }
    info[x][y] = sum;//被刮开的数
    //查询
    for (int i=0;i<3;i++){
        cin>>x>>y;
        cout<<info[x][y]<<endl;
    }
    //金币数量
    cin>>x;
    if (x==1) t=info[1][1]+info[1][2]+info[1][3];
    else if (x==2) t=info[2][1]+info[2][2]+info[2][3];
    else if (x==3) t=info[3][1]+info[3][2]+info[3][3];
    else if (x==4) t=info[1][1]+info[2][1]+info[3][1];
    else if (x==5) t=info[1][2]+info[2][2]+info[3][2];
    else if (x==6) t=info[1][3]+info[2][3]+info[3][3];
    else if (x==7) t=info[1][1]+info[2][2]+info[3][3];
    else t=info[1][3]+info[2][2]+info[3][1];
    cout<<res[t-6]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

5、乘法口诀数列

在这里插入图片描述
【输入样例】
2 3 10
【输出样例】
2 3 6 1 8 6 8 4 8 4

思路：分别设置cnt对乘积计数存储，out使每次输出1位并存储。记得数组要开够空间！

int main(){
    int a[100001],n,t,out=1,cnt=2; //数组设置长度要够
    cin>>a[0]>>a[1]>>n;
    if (n>0) cout<<a[0];//防止下标越界
    while (out<n){//没有输出完成指定个数
        t = a[out-1]*a[out];
        if (t/10){ //两位数
            a[cnt++] = t/10;
            t %= 10;
        }
        a[cnt++] = t;
        cout<<" "<<a[out];
        out += 1;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6、连续因子

一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。
【输入样例】
630
【输出样例】
3
567

思路：暴力遍历2到int(sqrt(n))+1，若没有这样的连续因子则为素数，记得此连续因子之积<n！！！

int main(){
    int n,maxi=0,start=1,p,q,t;
    cin>>n;
    for (int i=2;i<int(sqrt(n))+1;i++){
        if (n%i==0){ //非素数
            p=1,q=i+1,t=n/i;
            while (t%q==0){ //连续因子
                t/=q;
                p+=1;
                q+=1;
            }
            if (p>maxi){ //可以除尽，找最长连续
                maxi=p;
                start=i;
            }
        }
    }
    if (maxi){ //合数
        cout<<maxi<<"\n"<<start;
        for (int i=1;i<maxi;i++) cout<<"*"<<start+i;
    }
    else cout<<1<<"\n"<<n; //素数
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

7、矩阵乘法

【输入格式】
输入先后给出两个矩阵A和B。每个矩阵首先在一行中给出其行数R和列数C，随后R行每行给出C个整数，以1个空格分隔，且行首尾没有多余空格。输入保证两个矩阵的R和C都是正数，并且所有整数的绝对值不超过100。
【输出格式】
若输入的两个矩阵的规模是匹配的，则按照输入的格式输出乘积矩阵AB，否则输出Error: Ca != Rb，其中Ca是A的列数，Rb是B的行数。
【输入样例1】
2 3
1 2 3
4 5 6
3 4
7 8 9 0
-1 -2 -3 -4
5 6 7 8
【输出样例1】
2 4
20 22 24 16
53 58 63 28
【输入样例2】
3 2
38 26
43 -5
0 17
3 2
-11 57
99 68
81 72
【输出样例2】
Error: 2 != 3

思路：按题目所给输入存储后，判断能否相乘，若可相乘则利用三重循环求得结果矩阵的逐位结果。

int main(){
    //矩阵输入
    int a,b,c,d;
    cin>>a>>b;
    int A[a+1][b+1];
    for (int i=1;i<=a;i++){
        for (int j=1;j<=b;j++) cin>>A[i][j];
    }
    cin>>c>>d;
    int B[c+1][d+1];
    for (int i=1;i<=c;i++){
        for (int j=1;j<=d;j++) cin>>B[i][j];
    }

    if (b!=c) cout<<"Error: "<<b<<" != "<<c;
    else{
        int C[a+1][d+1]; //存储结果
        //矩阵乘法用三重循环
        for (int i=1;i<=a;i++){
            for (int j=1;j<=d;j++){
                C[i][j]=0;
                for (int k=1;k<=b;k++) C[i][j]+=A[i][k]*B[k][j];
            }
        }
        //结果输出
        cout<<a<<" "<<d<<endl;
        for (int i=1;i<=a;i++){
            for (int j=1;j<d;j++) cout<<C[i][j]<<" ";
            cout<<C[i][d]<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

8、天梯赛座位分配

假设某赛场有 N 所学校参赛，第 i 所学校有 M[i] 支队伍，每队 10 位参赛选手。令每校选手排成一列纵队，第 i+1 队的选手排在第 i 队选手之后。从第 1 所学校开始，各校的第 1 位队员顺次入座，然后是各校的第 2 位队员…… 以此类推。如果最后只剩下 1 所学校的队伍还没有分配座位，则需要安排他们的队员隔位就坐。本题就要求你编写程序，自动为各校生成队员的座位号，从 1 开始编号。
【输入格式】
输入在一行中给出参赛的高校数 N （不超过100的正整数）；第二行给出 N 个不超过10的正整数，其中第 i 个数对应第 i 所高校的参赛队伍数，数字间以空格分隔。
【输出格式】
从第 1 所高校的第 1 支队伍开始，顺次输出队员的座位号。每队占一行，座位号间以 1 个空格分隔，行首尾不得有多余空格。另外，每所高校的第一行按“#X”输出该校的编号X，从 1 开始。
【输入样例】
3
3 4 2
【输出样例】
#1
1 4 7 10 13 16 19 22 25 28
31 34 37 40 43 46 49 52 55 58
61 63 65 67 69 71 73 75 77 79
#2
2 5 8 11 14 17 20 23 26 29
32 35 38 41 44 47 50 53 56 59
62 64 66 68 70 72 74 76 78 80
82 84 86 88 90 92 94 96 98 100
#3
3 6 9 12 15 18 21 24 27 30
33 36 39 42 45 48 51 54 57 60

一个二维数组存结果、一维数组存下标，特殊样例为：

【输入1】1 0
【输出1】
【输入2】2 1 2
【输出2】
#1
1 3 5 7 9 11 13 15 17 19
#2
2 4 6 8 10 12 14 16 18 20
22 24 26 28 30 32 34 36 38 40
【输入3】2 2 1
【输出3】
#1
1 3 5 7 9 11 13 15 17 19
21 23 25 27 29 31 33 35 37 39
#2
2 4 6 8 10 12 14 16 18 20

int main(){
    //输入
    int n,num,now=1,maxn=101;
    cin>>n;
    num=n;
    int in[maxn],visit[maxn],res[maxn][maxn],cnt[maxn],where=0;
    memset(cnt,0,sizeof(cnt));
    memset(visit,0,sizeof(visit));
    for (int i=0;i<n;i++)  cin>>in[i];

    //循环存入
    while (num>1){
        for (int i=0;i<10;i++){
            for (int j=0;j<n;j++){
                if (in[j]>0){
                    if (i==9) in[j]-=1;//学校减少一支队伍
                    res[j][cnt[j]++]=now++;
                }
            }
        }
        for (int i=0;i<n;i++){
            if (in[i]==0&&!visit[i]){//去掉一个学校
                num-=1;
                visit[i]=1;
            }
            else if (in[i]!=0) where=i;//还有队伍的学校
        }
    }
    if (num&&in[where]>0){//还有学校
        if (cnt[where]&&res[where][cnt[where]-1]==now-1) now+=1;//要让此学校人间隔分开
        while (in[where]>0){
            for (int i=0;i<10;i++){
                res[where][cnt[where]++]=now;
                now+=2; //安排隔座位
            }
            in[where]-=1;
        }
    }
    //输出结果
    for (int i=0;i<n;i++){
        if (cnt[i]){
            cout<<"#"<<i+1<<endl;//有队伍才输出
            for (int j=0;j<cnt[i];j++){
                if ((j+1)%10==0&&(j+1)/10!=0) cout<<res[i][j]<<endl;
                else cout<<res[i][j]<<" ";
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

9、整除光棍

光棍是全部由1组成的数字，比如1、11、111、1111等。读入一个整数x，这个整数一定是奇数并且不以5结尾，经过计算输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。
提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。
【输入样例】
31
【输出样例】
3584229390681 15

思路：逐步增大位数会在位数大时超时。可以先使其增大至比x大，然后逐个商输出，将余数不断增大来减小计算量，记得判断条件是除数是否为0！

int main(){
    ll x,cnt=1,y=1;
    cin>>x;
    while (y<x){ //使得除数比被除数大
        y = y*10+1;
        cnt += 1;
    }
    while (y){ //增加1位数
        cout<<y/x; //先输出当前位
        y %= x; //将y变小
        if (y==0) break; //y=0就别再变1啦
        y = y*10+1;
        cnt+=1;
    }
    cout<<" "<<cnt;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

10、N个数求和最大公因数板子题

最大公因数函数：

ll gcd(ll x,ll y){return y ? gcd( y , x%y ) : x ;}

在这里插入图片描述
【输入样例1】
5
2/5 4/15 1/30 -2/60 8/3
【输出样例1】
3 1/3
【输入样例2】
2
4/3 2/3
【输出样例2】
2
【输入样例3】
3
1/3 -1/6 1/8
【输出样例3】
7/24

思路：使用gcd判断函数+long long类型存储，每次输入新分数就通分相加，全乘起来再累加分子会超过long long存储范围且超时！记得结果输出时将分子分母化简。

typedef long long ll;
ll gcd(ll x,ll y){return y ? gcd(y,x%y):x;}
int main(){
    ll n,total,sum=0,t,left,right;
    cin>>n;
    char b;
    ll a[n+1],c[n+1];
    //分情况讨论
    if (n==0) cout<<0;
    else{
        cin>>a[0]>>b>>c[0];
        left = a[0];
        right = c[0];
        for (ll i=1;i<n;i++){
            cin>>a[i]>>b>>c[i];
            //两个分数交叉相乘
            left = left*c[i]+right*a[i];
            right *= c[i];
            t = gcd(left,right);
            left /= t;
            right /= t;
        }
        if (left%right==0) cout<<left/right; //整数部分
        else{
            t = gcd(left%right,right);
            if (left/right==0) cout<<(left%right)/t<<"/"<<right/t; //分数部分
            else cout<<left/right<<" "<<(left%right)/t<<"/"<<right/t; //都有
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

11、阅览室

当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。
注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。
【输入格式】
输入在第一行给出一个正整数N（≤10），随后给出N天的纪录。每天的纪录由若干次借阅操作组成，每次操作占一行，格式为：
书号（[1, 1000]内的整数）键值（S或E）发生时间（hh:mm，其中hh是[0,23]内的整数，mm是[0, 59]内整数）
每一天的纪录保证按时间递增的顺序给出。
【输出格式】
对每天的纪录，在一行中输出当天的读者借书次数和平均阅读时间（以分钟为单位的精确到个位的整数时间）。
【输入样例】
3
1 S 08:10
2 S 08:35
1 E 10:00
2 E 13:16
0 S 17:00
0 S 17:00
3 E 08:10
1 S 08:20
2 S 09:00
1 E 09:20
0 E 17:00
【输出样例】
2 196
0 0
1 60

思路：输入分为5个部分，分类讨论0 S E三种情况，注意四舍五入输出写法。坑点：多次借书一次还书，则记录最后一次借书时间。

#include <bits/stdc++.h>
#define maxn 1001
int book[maxn];
int main(){
    int n,a,c,e;
    double sum,cnt;
    char b,d;
    cin>>n;
    while (n--){
        sum=0,cnt=0;
        memset(book,-1,sizeof(book)); //每天记录清零
        while (cin>>a>>b>>c>>d>>e){
            if (a==0) break; //一天结束
            if (a<0||a>1000) continue; //书的编号不合法
            if (b=='S') book[a]=c*60+e;//借书可以多次重复
            else if (b=='E' && book[a]!=-1){//还书
                sum += (c*60+e-book[a]);
                book[a] = -1;
                cnt += 1;
            }
        }
        if (cnt) cout<<int(cnt)<<" "<<int(double(sum/cnt)+0.5)<<endl;
        else cout<<"0 0\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

13、非常弹的球（靠，居然还有物理题我物理太烂了）

刚上高一的森森为了学好物理，买了一个“非常弹”的球。虽然说是非常弹的球，其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到，假如他在地上用力弹球，球最远能弹到多远去呢？他不太会，你能帮他解决吗？当然为了刚学习物理的森森，我们对环境做一些简化：
假设森森是一个质点，以森森为原点设立坐标轴，则森森位于(0, 0)点。
小球质量为w/100 千克（kg），重力加速度为9.8米/秒平方（m/s^2）。
森森在地上用力弹球的过程可简化为球从(0, 0)点以某个森森选择的角度ang (0<ang<π/2) 向第一象限抛出，抛出时假设动能为1000 焦耳（J）。
小球在空中仅受重力作用，球纵坐标为0时可视作落地，落地时损失p%动能并反弹。
地面可视为刚体，忽略小球形状、空气阻力及摩擦阻力等。
森森为你准备的公式：
动能公式：E=m×v^2/2
牛顿力学公式：F=m×a
重力：G=m×g
其中：
E - 动能，单位为“焦耳”
m - 质量，单位为“千克”
v - 速度，单位为“米/秒”
a - 加速度，单位为“米/秒平方”
g - 重力加速度
【输入格式】
输入在一行中给出两个整数：1≤w≤1000 和 1≤p≤100，分别表示放大100倍的小球质量、以及损失动力的百分比p。
【输出格式】
在一行输出最远的投掷距离，保留3位小数。
【输入样例】
100 90
【输出样例】
226.757

设角度为 θ，速度分解得水平方向速度为vcosθ，竖直方向为vsinθ，在竖直方向上求得上升到最高点的时间为vsinθ/g（运动学公式v=gt），水平方向的距离s=vt=vcosθ2t = vvsin2θ/g。当θ为45度时sin2θ取最大值1，即球运动的水平距离：s=v* v/g，由Ek=m* v* v/2，得vv=2Ek/m，代入距离公式得：s=2* Ek/（m*g），每次循环让Ek缩小p%，取合适的精度跳出循环

#include <iomanip>
int main(){
	double w,p,ans,dis;
	cin>>w>>p;
	//s = 2*(m*v*v/2)/(m*g);
	dis=0;
	ans=2*1000*100/(w*9.8);
	while(ans>0.0000001){
		dis += ans;
		ans *= (100-p)/100;
	}
	cout<<fixed<<setprecision(3)<<dis;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

14、神坛三角形面积极角排序

在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好。特殊地，如果有两块神石坐标相同，或者三块神石共线，神坛的面积为 0.000。
长老们发现这个问题没有那么简单，于是委托你编程解决这个难题。
【输入格式】
输入在第一行给出一个正整数 n（3 ≤ n ≤ 5000）。随后 n 行，每行有两个整数，分别表示神石的横坐标、纵坐标（−10^9≤ 横坐标、纵坐标 <10 ^9 ）。
【输出格式】在一行中输出神坛的最小面积，四舍五入保留 3 位小数。
【输入样例】
8
3 4
2 4
1 1
4 1
0 3
3 0
1 3
4 2
【输出样例】0.500
【样例解释】输出的数值等于图中红色或紫色框线的三角形的面积。
在这里插入图片描述

把所有的三点组合求面积（分情况讨论），输出最小面积。暴力只能得13分。。。

#include <iomanip>
#include <cmath>
int X[5000],Y[5000],Z[5000];
double s(int x1,int y1,int x2,int y2,int x3,int y3){//计算三角形面积
    double my=max(y1,max(y2,y3)),ny=min(y1,min(y2,y3)),y=y1+y2+y3-my-ny;
    double mx,nx,x;
    if (my==y1) mx=x1;
    else if (my==y2) mx=x2;
    else mx=x3;
    if (ny==y1) nx=x1;
    else if (ny==y2) nx=x2;
    else nx=x3;
    x=x1+x2+x3-mx-nx;
    //计算
    if ((y1==y2&&y2==y3)||(x1==x2&&x2==x3)) return 0;//三石共线
    //两石共线
    else if (my==y) return abs(1.0*(mx-x)*(y-ny)/2.0);
    else if (y==ny) return abs(1.0*(x-nx)*(my-y)/2.0);
    else if (mx==x) return abs(1.0*(my-y)*(x-nx)/2.0);
    else if (x==nx) return abs(1.0*(y-ny)*(mx-x)/2.0);
    //普通情况
    double dx = mx-((my-ny)*(mx-x)/(my-y)),dy=ny;
    double S=(nx-dx)*(my-y)/2;
    return abs(S);
}
int main(){
    int n;
    cin>>n;
    double t,res=100000000;
    for (int i=0;i<n;i++){
        cin>>X[i];
        cin>>Y[i];
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<i;j++){
            for (int k=0;k<j;k++){
                t = s(X[i],Y[i],X[j],Y[j],X[k],Y[k]);
                if (t<res) res=t;
            }
        }
    }
    cout<<fixed<<setprecision(3)<<res;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

优化思路：极角排序求每个点为起点的面积，S=|x1y2-x2y1|* 1/2

在这里插入图片描述

bool cmp(node a,node b){return (a.dxb.dy>b.dxa.dy);} //点按顺时针排序

S三角形= 1/2 * |dx1 * dy2 - dx2 * dy1|

对本题的数据范围，要用long long，最后除以2用long double

#include <algorithm>
#include <iomanip>
#include <vector>
typedef long long ll;
ll X[5000],Y[5000],n;
struct node{ll dx,dy;};
bool cmp(node a,node b){return (a.dx*b.dy>b.dx*a.dy);}//点按顺时针排序
int main(){
    //输入
    cin>>n;
    ll t,res=1e18;
    for (int i=0;i<n;i++) cin>>X[i]>>Y[i];
    //仅计算相邻点组成的三角形
    for (int i=0;i<n;i++){//以每个点作为起点
        vector<node> v;
        for (int j=0;j<n;j++){
            if (i!=j) v.push_back({X[i]-X[j],Y[i]-Y[j]});
        }
        sort(v.begin(),v.end(),cmp);
        for (int j=1;j<v.size();j++){
            t = (v[j].dx*v[j-1].dy-v[j].dy*v[j-1].dx);//求面积
            if (t<0) t=-t;
            if (res>t) res=t;
        }
    }
    long double ans = res*1.0/2.0;
    cout<<fixed<<setprecision(3)<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/328830