首页 > 代码库 > bzoj 1132 POI2008 Tro
bzoj 1132 POI2008 Tro
大水题=_=，可我想复杂了……
很裸的暴力，就是加了个小优化……
叉积求面积 ：abs（xi*yj - yi*xj） 所以去掉绝对值，把 xi 和 xj 提出来就可以求和了
去绝对值加个极角排序，每次把最左边的点当成原点，然后剩下的排序，接着枚举第二个点，求叉积之和……
坐标都是整数，用long long，最后再除2
上代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define N 3010using namespace std;struct sss{ long long x, y;}dian[N], now, zan[N];int n;long long ans = 0;long long chaji(sss x, sss y){ return (x.x-now.x)*(y.y-now.y) - (x.y-now.y)*(y.x-now.x);}bool cmp1(sss x, sss y) { return x.x == y.x ? x.y < y.y : x.x < y.x; }bool cmp2(sss x, sss y ){ return chaji(x, y) > 0; }int main(){ scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld%lld", &dian[i].x, &dian[i].y); sort(dian+1, dian+1+n, cmp1); for (int i = 1; i <= n-2; ++i) { now = dian[i]; long long ty = 0, tx = 0; for (int j = i+1; j <= n; ++j) zan[j] = dian[j]; sort(zan+i+1, zan+1+n, cmp2); for (int j = i+1; j <= n; ++j) { ty += zan[j].y-now.y; tx += zan[j].x-now.x; } for (int j = i+1; j <= n-1; ++j) { ty -= zan[j].y-now.y; tx -= zan[j].x-now.x; ans += (zan[j].x-now.x)*ty - (zan[j].y-now.y)*tx; } } if (ans % 2) printf("%lld.5\n", ans/2); else printf("%lld.0\n", ans/2);}
bzoj 1132 POI2008 Tro
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。