[BZOJ1132 [POI2008]Tro]利用极角排序去绝对值

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1132
【解题经历】
先YM LCC大牛。。。
表示一直不会极角排序，做凸包我都是用按Y坐标排，然后弄上壳和下壳的那种。。。
然后YY了比较久，感觉很难。。。。
于是去围观LCC大牛的代码，OH。。。原来这么简单。
【算法分析】
实际上我之前想的都陷入了一个误区，那就是原点是任意的，而LCC大牛的代码中是取左上角的那个点做原点，那么所有的点都会在同一象限，那么直接用叉积就可以判断了（因为角度都0<=α<=π/2，叉积不会出现分两边的问题）。
现在看这道题，假设枚举一个点k，那么ans+=SUM(abs(Xi*Yj-Yi*Xj)) (1<=i然后我们对于点i，所要加的面积应该是Xi*((Yi+1) + (Yi+2) +….+ (Yn))  -  Yi*((Xi+1) + (Xi+2) + … + (Xn))。
好吧，维护和就可以。
然后要注意的是，极角排序是选定了左上角那个点的，然后每次都去掉这个基准点就可以不断进行，且没有重复，使得最后剩下<3个点，就是结果了。
【其他】。。。时间排最后几位，表示不明真相，为啥LCC大牛这么快呢。。。55555
【CODE】
#include using namespace std;
typedef __int64 lld;
const int N=3005;
int n;
struct Point{lld x,y;}P[N];
lld ans=0;

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%I64d%I64d",&P[i].x,&P[i].y);
}

bool cmp(Point a,Point b){return a.x*b.yvoid count(int n){
lld Sx=0,Sy=0,i,k=1,S;
for (i=1;i<=n;i++)
if (P[i].x swap(P[k],P[n]);
for (i=1;i P[i].x-=P[n].x;
P[i].y-=P[n].y;
}
sort(P+1,P+n,cmp);
for (i=1;i ans+=P[i].x*Sy-P[i].y*Sx;
Sx+=P[i].x;
Sy+=P[i].y;
}
}

int main(){
input();
for (int i=n;i>=1;i–) count(i);
if (ans%2==1) printf("%I64d.5n",ans/2);
else printf("%I64d.0n",ans/2);
}