UVa1606 Amphiphilic Carbon Molecules（极角排序+扫描线）
题目链接
题目大意
平面上有一系列点，要么是黑点要么是白点，假设可以在平面上放置一条直线，使得直线某侧的黑点加上另一侧的白点数目最多（直线上的点可以算作任意一侧）。
解题思路
先分析一下LRJ老师的思路：假设隔板至少经过两个点，那么最简单的想法是枚举任意两个点构成的直线并按题意统计，时间复杂度 O ( n 3 ) O(n^3) O(n3)，肯定超时。那么，先枚举一个基准点，将一条直线绕这个点旋转，每当直线扫过一个点，就可以动态修改。由于扫描直接要先相对于基准点极角排序，再加上基准点的 n n n种取法，时间复杂度 O ( n 2 l o g n ) O(n^2logn) O(n2logn)，此题有三大核心：
- 坐标变换
- 极角排序
- 扫描线动态维护答案
首先说一下坐标变换和极角排序，因为隔板是条直线，选择一个点作为基准点后，再任选一个点就构成了隔板。但是平面上的点是任意分布的，直接遍历在统计时会出现重复统计等各种问题，因此先极角排序，使所有点相对于基准点形成逆时针的序列。在排序之前要预处理坐标得到坐标相对于基准点的新坐标，此外像上面博客那样在排序比较函数传入极点也可以。另外一个比较重要的优化是，因为两侧的黑点和白点是求和的，为了方便可以将所有黑点或者所有白点相对于基准点旋转180°，相当于变成了一种颜色的点，这样就直接统计隔板一侧的点即可（方便起见统计的是左侧，即逆时针的一侧），如下图可以得出隔板在旋转过程中统计一侧最后的答案不变。
本题最重要且最难懂的就是扫描线这里了，说难懂是因为没见过这种处理技巧，但是如果学过计算几何后，这部分其实是不难看懂的。极角排序之后，我们要先找隔板，那就和所有点都作一次隔板，接着呢，统计隔板左侧（也就是逆时针侧）的数量，判断是否在隔板左侧，因为我们已经将所有点按照基准点分布在一个新的坐标系中，那么就直接toLeftTest（判断点是否在直线左侧）即可，之所以toLeftTest里写的是大于等于，是因为在隔板上的点得到的值是0，但是我们要统计到数量中去。因为隔板是逆时针转的，每向左转动一个点，上一个点就到了隔板右侧，因此直接将数量减一，至于转动后多了几个点，那就是后面统计计数的活了。另外需要注意，枚举隔板左边的点（实际上是向量）时，因为每次都转动一圈直到再到达隔板，因此要(r+1)%k，形成循环
5.最后的过程自己模拟一下很容易懂的，这里懒得作图了，因为静态图不是很容易看出来，做动图又太麻烦，如果想看静态图或者关于代码注释的去看一下这个博客，我也是看他的博客学习的
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define Point Vector
const int maxn=1005;
const double eps=1e-8;
struct Point{
int x,y;
int col;
double rad;
int operator ^ (Vector B){
return x*B.y-y*B.x;
}
};
Point p1[maxn],p2[maxn];
int n;
bool toLeftTest(Point a,Point b){
return (a^b)>=0;
}
bool cmp(Point a,Point b){
return a.rad<b.rad;
}
int solve(int m){
int ans=0,k=0;
for(int i=0;i<n;i++){
if(i==m) continue;
p2[k].x=p1[i].x-p1[m].x;
p2[k].y=p1[i].y-p1[m].y;
if(p1[i].col){
p2[k].x=-p2[k].x,p2[k].y=-p2[k].y;
}
p2[k].rad=atan2(p2[k].y,p2[k].x);
k++;
}
sort(p2,p2+k,cmp);
int l=0,r=0,cnt=2;
while(l<k){
if(r==l) r=(r+1)%k,cnt++;
while(r!=l && toLeftTest(p2[l],p2[r])){
r=(r+1)%k;
cnt++;
}
cnt--;
l++;
ans=max(ans,cnt);
}
return ans;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while(cin>>n){
if(!n) break;
for(int i=0;i<n;i++)
cin>>p1[i].x>>p1[i].y>>p1[i].col;
if(n<=3){
cout<<n<<endl;
continue;
}
int ans=0;
for(int i=0;i<n;i++){
ans=max(solve(i),ans);
}
cout<<ans<<endl;
}
return 0;
}