裸的做是 O(n3) 按极角排序后 用分配律 就可以 O(n2logn)
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int N=3005; struct PP{ int x,y; PP(int x=0,int y=0):x(x),y(y) { } bool read() { int _x,_y; if (scanf("%d%d",&_x,&_y)==-1) return 0; x=_x; y=_y; return 1; } PP operator - () { return PP(-x,-y); } friend PP operator + (PP A,PP B) { return PP(A.x+B.x,A.y+B.y); } friend PP operator - (PP A,PP B) { return PP(A.x-B.x,A.y-B.y); } friend PP operator * (PP A,int B) { return PP(A.x*B,A.y*B); } friend PP operator / (PP A,int B) { return PP(A.x/B,A.y/B); } friend int operator * (PP A,PP B) { return A.x*B.x+A.y*B.y; } friend ll det(PP A,PP B) { return (ll)A.x*B.y-(ll)A.y*B.x; } }a[N],b[N]; bool cmp(PP A,PP B){ return A.y<B.y||(A.y==B.y&&A.x<B.x); } bool cmp_(PP A,PP B){ return det(A,B)>0; } int n,m; ll ans; int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) a[i].read(); sort(a+1,a+n+1,cmp); for (int i=1;i<=n-2;i++){ PP sum=PP(0,0); int tot=0; for (int j=i+1;j<=n;j++) b[++tot]=a[j]-a[i]; sort(b+1,b+tot+1,cmp_); for (int j=1;j<=tot;j++) ans+=det(sum,b[j]),sum=sum+b[j]; } printf("%lld.%d\n",ans>>1,ans&1?5:0); return 0; }