ICPC2018西南欧洲赛区F. Paris by Night（极角排序）

题目链接

https://codeforces.com/gym/102465/problem/F

题解

思路很简单。枚举一个定点，完了一这个点为原点把其他点极角排序。然后按极角序枚举第二点形成分界边。这样直线一边包含的点是可以单调维护的。设置左右两个指针，分别是在当前分界向量（有第一点指向第二点）逆时针旋转180的点的起始和终止（像单调队列）。在边的一侧可以用向量叉积与0的关系来看。如果向量旋转角度是小于180的话，按右手定则叉积大于0。注意要弄两遍循环一下，因为可能转弯一圈回来了。可以当做极角排序的板子。

吐槽

计算几何是一类极度考验选手心理素质和代码能力，以及思维清晰度的问题。细节繁多，代码量巨大。很可能一直卡住调不出来。这场应该是法国人出的，题面就有一股浓浓的资本主义浮华迷醉的油腻风格，动不动就是大巴黎的纪念碑，美术馆，石雕之类。。。感觉这道题挺难写的，不知道为啥赛场上过那么多人。资本主义的奢华，咱这种勤劳朴实的无产阶级小知识分子是无法理解的，因为题目真心看不懂。

AC代码

网上抄的极角排序板子，调到代码千疮百孔。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 50; struct point { ll x, y, val; point(ll x = 0, ll y = 0): x(x), y(y) {} bool operator < (const point &b) const { return y - b.y == 0 ? x - b.x < 0 : y - b.y < 0; } //向量+ point operator + (const point &b) const { return point(x + b.x, y + b.y); } //向量- point operator - (const point &b) const { return point(x - b.x, y - b.y); } //叉积 ll operator ^ (const point &b) const { return x * b.y - y * b.x; } //点积 ll operator * (const point &b) const { return x * b.x + y * b.y; } //两点间距离 ll dist(point b) { return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y); } void input() { scanf("%lld%lld%lld",&x,&y,&val); } void ouput() { printf("%lld %lld %lld\n", x, y, val); } }; point p[N]; point tmp[N]; int qua(point a) { ll x = a.x, 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; } point c; bool cmp(point a, point b) { ll d = (a - c) ^ (b - c); if (d == 0) return a.dist(c) < b.dist(c); return d > 0; } bool cmp1(point a, point b) { point x = a - c; point y = b - c; if (qua(x) == qua(y)) return cmp(a, b); return qua(x) < qua(y); } //按极角排序，先找到最左下角的点 //重载point的< int n; void norm(int k) { c = tmp[k]; sort(tmp + 1, tmp + n + 1, cmp1); } int main() { scanf("%d",&n); for (int i = 1; i <= n; i++) p[i].input(); ll tot = 0; ll ans = 100000000000000ll; for (int i = 1; i <= n; i++) tot += p[i].val; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++){tmp[j] = p[j];} norm(i); for(int j=2;j<=n;j++)tmp[j+n-1]=tmp[j]; /*printf("\n"); for (int j = 1; j <= n; j++) tmp[j].ouput(); printf("\n");*/ int l=3,r=2; while(1){ if(r==2*n-1)break; if((tmp[r+1].y-tmp[1].y)*(tmp[2].x-tmp[1].x)-(tmp[r+1].x-tmp[1].x)*(tmp[2].y-tmp[1].y)<=0 ){ break; } r=r+1; } long long sum1=0;long long sum2=0; for(int j=l;j<=r;j++)sum1+=tmp[j].val; sum2=tot-sum1-tmp[1].val-tmp[2].val; //printf("*%d %d %lld %lld\n",l,r,sum1,sum2); for(int j=3;j<=n;j++){ l=j+1; sum1-=tmp[j].val; if(r<l-1){ for(int k=r+1;k<=l-1;k++)sum1+=tmp[k].val; r=l-1; } int lr=r; int curx=tmp[j].x-tmp[1].x; int cury=tmp[j].y-tmp[1].y; while(1){ if(r==2*n-1)break; if((tmp[r+1].y-tmp[1].y)*curx-(tmp[r+1].x-tmp[1].x)*cury<=0 ){ break; } r=r+1; } for(int j=lr+1;j<=r;j++)sum1+=tmp[j].val; sum2=tot-sum1-tmp[1].val-tmp[j].val; ans=min(ans,abs(sum1-sum2)); //if(abs(sum1-sum2)==1)printf("********\n"); //printf("*%d %d %lld %lld\n",l,r,sum1,sum2); } //ans=min(ans,res); } printf("%lld\n", ans); return 0; }