L3-021 神坛 (30 分)
程序员文章站
2022-04-01 10:44:06
...
思路:暴力枚举是O(n^3),会 t,于是换一种枚举方式:可以取每个点作为极点,然后将其他点进行极角排序,相邻两向量的叉积的一半就是一个三角形的面积,这样枚举可以不漏而且将复杂度降到O(n^2)
这里因为输入的都是正整数,所以不需要用double读入(会被卡),最后乘以0.5的时候转成double就行_(:з」∠)_
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 5010;
typedef long long ll;
typedef struct
{
ll x, y;
}P;
P p[maxn];
ll px[maxn], py[maxn];
double ans;
int qua(P a)
{
ll x = a.x;
ll y = a.y;
if(x > 0 && y >= 0) return 1;
if(x <= 0 && y > 0) return 2;
if(x < 0 && y <= 0) return 3;
if(x >= 0 && y < 0) return 4;
}
ll cross(P a, P b)
{
return a.x * b.y - a.y * b.x;
}
bool cmp(P a, P b)
{
if(qua(a) == qua(b))
return cross(a, b) < 0;
return qua(a) < qua(b);
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 1;i <= n; i++)
{
ll x, y;
scanf("%lld%lld", &x, &y);
px[i] = x;
py[i] = y;
}
double ans = 1e18;
for(int i = 1;i <= n; i++)
{
int cnt = 0;
for(int j = 1;j <= n; j++)
{
if(i == j) continue;
cnt++;
p[cnt].x = px[j] - px[i];
p[cnt].y = py[j] - py[i];
}
sort(p + 1, p + 1 + cnt, cmp);
for(int j = 1;j < cnt; j++)
{
ans = min(ans, fabs(cross(p[j], p[j + 1]) * 0.5));
}
}
printf("%.3lf\n", ans);
return 0;
}
上一篇: poj1981-单位圆最多覆盖点
下一篇: numpy中的mean()函数