UVA1606 （Amphiphilic Carbon Molecules）（极角排序，扫描法）
题目大意：平面上有n个点，每个点为白点或者黑点。现在需放置一条隔板，使得隔板一侧的白点数加上另一侧的黑点数总书最大。隔板上的点可以看作是在任意一侧。
思路分析：
（1）、如果枚举两点，以两点所在的直线作为隔板，统计隔板两侧的点的分布，时间复杂度为O(n3），会超时。
（2）、通过枚举基准点，以基准点为坐标系原点，计算其余点的相对坐标，并按照极角排序。将基准点和除基准点的另外一个点的连线作为隔板，扫描整张图，动态维护点的数量。
（3）、可以将黑点以隔板为对称轴进行坐标的对称变换，这样，只需扫描隔板的一侧即可。
（4）、动态维护扫描到点的数量cnt，在基准线（隔板）变换时，只需cnt–
（5）、扫描法即为带有顺序的枚举法，在枚举时可以维护一些量，使得计算简化，避免进行重复的运算。
（6）、在进行极角排序时，有两种方法：
1、用atan2函数（在cmath头文件中）进行排序，传入纵坐标y为第一个参数，横坐标x为第二个参数，返回y/x的反正切，取值时(-pi，pi]从第三象限逆时针旋转成递增关系。
2、使用二维向量叉乘，有向量a(x1,y1),b(x2,y2)，则a×b=x1y2-x2y1。如果a×b大于0，则从a边到b边（沿顺时针方向）的夹角小于pi；如果a×b等于0，则a与b共线；如果a×b小于0，则从a边为起始边到b边的夹角大于pi；
atan2的速度快，但精度不佳；
用向量叉乘速度慢，但精度可以。
#include<bits/stdc++.h>
using namespace std;
struct Node{int x,y,r;double k;bool operator <(const Node &p) const{return k<p.k;}
};
Node node[1005];
Node re_pos[1005]; //相对位置
int n;
bool is_left(Node a,Node b)//向量叉乘 a×b=a*b*sina 如果叉乘小于零，则a与b的夹角大于180
{return a.x*b.y-b.x*a.y>=0;
}
int solve(void)
{if(n<=3)return n;int ans=0;for(int i=0;i<n;i++)//选取基准点{int index=0;for(int j=0;j<n;j++)if(j!=i){re_pos[index].x=node[j].x-node[i].x;re_pos[index].y=node[j].y-node[i].y;if(node[j].r){re_pos[index].x=-re_pos[index].x;re_pos[index].y=-re_pos[index].y;}re_pos[index].k=atan2(re_pos[index].y,re_pos[index].x);index++;}sort(re_pos,re_pos+index);int l=0;//隔板（基准轴）int r=0;//旋转轴int cnt=2;//计数，初始为基准轴上的两个while(l<index)//枚举基准轴{if(l==r){r=(r+1)%index;//旋转操作取模 cnt++;}while(l!=r&&is_left(re_pos[l],re_pos[r])){r=(r+1)%index;cnt++;}cnt--;//?????ans=max(ans,cnt);l++;} }return ans;
}
int main(void)
{
// freopen("out.txt","w",stdout);while(~scanf("%d",&n)&&n){int x,y,r;int cnt_0=0,cnt_1=0;for(int i=0;i<n;i++)scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].r);printf("%d\n",solve());}
// fclose(stdout);
}
//3
//0 0 0
//0 1 0
//2 2 1
//4
//0 0 0
//0 4 0
//4 0 0
//1 2 1
//7
//-1 0 0
//1 2 1
//2 3 0
//2 1 1
//0 3 1
//1 4 0
//-1 2 0
//0
在代码中，注意l等于r时，cnt要进行递增，这里一开始是迷惑我的地方。
有两种情况会出现l==r：
1、在开始的时候。如果仅仅考虑这种情况，那么在l=r时，对cnt进行递增看起来是多余的操作，仅仅需要把cnt递减的操作放在判断ans后就行了。
2、l也会出现追赶上r的情况。r如果在l的180开外，那么只能l进行递增，而r不动，当追赶上r时，如果不在l=r时进行cnt递增的操作，那么cnt的值为1，从而后续的cnt都是错的。你可以自己试试。
还有一种办法是，在l=r时，将cnt的值设定为2.
有个疑问，叉乘排出来的序列感觉不是严格递增的，如果a×b>0,a×c<0,但是可能b×c>0,那怎么能扫描呢