这道题的关键是用到了极角排序的方法，枚举一个固定点，其他点以此点为原心求出角度，，然后排序，将数点的多少转化为数角度的多少。因为角度是有序的，便可以用一次扫描求出最大值。另外，还用到了一个小技巧，那就是利用对称性，将一侧的黑点转化成另一侧的白点，这样只需要数白点的个数就好了。
值得注意的是，为了形成那条分界线，我们枚举两个角度（也就是由基准点为原心的新坐标系中的点） ，使他们之间的夹角不超过180°，为了使分界线旋转360°，我们将l变量枚举到最后一个点再停，所以r变量的自加变成了（r+1）%cnt
如图，由于已经将黑点对称变换到另一侧，所以这个锐角范围内的点的个数就是答案。这相当于一个并不直的挡板。
#include<bits/stdc++.h>using namespace std;const int maxn = 1000 + 5;int n;struct point{int x,y,col;double rad;bool operator < (const point &r) const {return rad < r.rad;}}p[maxn],op[maxn];bool X(int l,int r){return p[l].x*p[r].y-p[l].y*p[r].x >= 0 ;}int main(){while(~scanf("%d",&n)&&n){for(int i=0;i<n;i++) scanf("%d%d%d",&op[i].y,&op[i].x,&op[i].col);if(n<=2) { printf("%d",n) ; continue; }int ans = 0;for(int i=0;i<n;i++) {int cnt = 0;for(int j=0;j<n;j++){if(i!=j) {p[cnt].x = op[j].x – op[i].x;p[cnt].y = op[j].y – op[i].y;if(op[j].col == 1) {p[cnt].x = -p[cnt].x;p[cnt].y = -p[cnt].y;}p[cnt].rad = atan2(p[cnt].y,p[cnt].x);cnt++;}}sort(p,p+cnt);int sum = 2,l = 0,r = 0;while(l < cnt){if(l==r) { r = (r+1)%cnt; sum++; } //为了枚举360°while(l!=r&&X(l,r)) {r = (r+1)%cnt; sum++;}l++; //当超过180°时，sum–;//减掉不在锐角内的点ans = max(ans,sum);}}printf("%d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
靠山山会倒，靠人人会跑，只有自己最可靠。
