链接 : 地址
紫书题，很经典
题意 p-238 就是给你N个点有黑有白，给你一个挡板，问挡板一边黑子加一边白子的最大值是？挡板上的可看做任意一边的
方法 随便选一个点作为原点 把所有坐标转化成相对坐标，再选一个点连起来作为一个轴，然后旋转
参考:https://blog.csdn.net/u014800748/article/details/47952253
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
#define ll long long
#define inf 0x3f3f3f3f
int n;
void intt()
{freopen("in","r",stdin);}
struct point{
int x;
int y;
int id;
double ta;}ss[1100],p[1100];
bool cmp(point a,point b)
{return a.ta<b.ta;}
int solve()
{int ans=0;for(int i=0;i<n;i++) //选点作为原点{int k=0;for(int j=0;j<n;j++) //转化为相对坐标{if(i!=j){p[k].x=ss[j].x-ss[i].x;p[k].y=ss[j].y-ss[i].y;if(ss[j].id) {p[k].x=-p[k].x;p[k].y=-p[k].y;}p[k].ta=atan2(p[k].y,p[k].x);k++;}}sort(p,p+k,cmp); //按照tan排序int L=0;int R=0;int cnt=2; //L 轴 R旋转扫描符合的点while(L<k){if(L==R) {R=(R+1)%k;cnt++;}while(L!=R&&(p[L].x*p[R].y-p[L].y*p[R].x>=0)){R=(R+1)%k;cnt++;}cnt--; //每次都会转到第一个不符合的点，减一去掉L++;ans=max(ans,cnt);}}return ans;
}
int main()
{while(cin>>n&&n){for(int i=0;i<n;i++){cin>>ss[i].x>>ss[i].y>>ss[i].id;}printf("%d\n",solve());}return 0;
}