「BZOJ1132」[POI2008] Tro
Description
平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和 N<=3000
Input
第一行给出数字N,N在[3,3000] 下面N行给出N个点的坐标,其值在[0,10000]
Output
保留一位小数,误差不超过0.1
Sample Input
5
0 0
1 2
0 2
1 0
1 1
0 0
1 2
0 2
1 0
1 1
Sample Output
7.0
题解
叉积求面积 ：abs（xi*yj – yi*xj） 所以去掉绝对值，把 xi 和 xj 提出来就可以求和了
每次把最左边的点当成原点，然后剩下的极角排序，接着枚举第二个点，求叉积之和……
坐标都是整数，用long long，最后再除2
|
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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,sumx,sumy; ll ans; struct P{int x,y;}p[3005],t[3005]; ll operator*(P a,P b) { return a.x*b.y-a.y*b.x; } bool operator<(P a,P b) { return a.y<b.y||(a.y==b.y&&a.x<b.x); } bool cmp(P a,P b) { return a*b>0; } void solve() { sort(p+1,p+n+1); for(int i=1;i<=n-2;i++) { int top=0;sumx=sumy=0; for(int j=i+1;j<=n;j++) { top++; t[top].x=p[j].x-p[i].x; t[top].y=p[j].y-p[i].y; } sort(t+1,t+top+1,cmp); for(int j=1;j<=top;j++) { sumx+=t[j].x; sumy+=t[j].y; } for(int j=1;j<=top;j++) { sumx-=t[j].x; sumy-=t[j].y; ans+=(ll)t[j].x*sumy-(ll)t[j].y*sumx; } } } int main() { n=read(); for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); solve(); if(ans&1)printf("%lld.5",ans/2); else printf("%lld.0",ans/2); return 0; } |
Subscribe
计数器 9313245
OI 课件=>
OI 课件=>