题目：点击查看题目
思路：这道题的解决思路是极角扫描法。极角扫描法的思想主要是先选择一个点作为基准点，然后求出各点对于该点的相对坐标，同时求出该坐标系下的极角，按照极角对点进行排序。然后选取点与基准点形成的线对点进行扫描，基准线为遍历选取，扫描线扫过的点，减去基准线扫过的点即为所要求的点的数量。同时注意到我们要求的是线两边的两种点的数量，于是一种点比如黑点可以旋转180度，然后之考察这180度内的百点数量即可。本题的基准点选取复杂度为O(n)，极角排序复杂度O(nlogn)，扫描复杂度O(n)，复杂度为O(N2logN + N2)，可视为O(N2logN)
AC代码：
#include <iostream>
#include <cmath>
#include <algorithm> using namespace std; const int maxn = + ; struct point{
int x, y, color;
double angle;
bool operator < (const point& temp) const {
return angle < temp.angle;
}
}point[maxn], cpoint[maxn]; bool judge(struct point& A, struct point& B) {
return A.x*B.y - A.y*B.x >= ;
} int solve(int n) {
if(n <= ) return n; int ans = ;
for(int i = ; i < n; i++) {
int index = ;
for(int j = ; j < n; j++) {
if(j == i) continue;
cpoint[index].x = point[j].x - point[i].x;
cpoint[index].y = point[j].y - point[i].y;
if(point[j].color) {
cpoint[index].x = -cpoint[index].x;
cpoint[index].y = -cpoint[index].y;
}
cpoint[index].angle = atan2(cpoint[index].y, cpoint[index].x);
index++;
}
sort(cpoint, cpoint+index); int st = , ed = , cnt = ;
while(st < index) {
if(st == ed) {
ed = (ed + )%index;
cnt++;
}
while(st != ed && judge(cpoint[st], cpoint[ed])) {
ed = (ed + )%index;
cnt++;
} cnt--;
st++; ans = max(ans, cnt);
}
}
return ans;
} int main()
{
int n;
while(cin >> n && n) {
for(int i = ; i < n; i++) {
cin >> point[i].x >> point[i].y >> point[i].color;
}
cout << solve(n) << endl;
}
return ;
}