紫书 例题8-6 UVa 1606（扫描法）

这道题目用扫描法

扫描法：在枚举的过程中维护一些重要的量， 从而简化计算

这道题用到了极角， 叉积， 高一的我表示一脸懵逼

不过自己去百度了一下好像大概看得懂。

这道题我还有一些疑问， 先这样吧

#include<cstdio>
#include<cmath> 
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 1123;
struct Point
{
	int x, y;
	double rad;
	bool operator < (const Point &rhs) const 
	{
		return rad < rhs.rad;
	}
}op[MAXN], p[MAXN];
int color[MAXN], n;

inline bool left(Point a, Point b)
{
	return a.x * b.y - a.y * b.x >= 0;
}

int solve()
{
	if(n <= 2) return 2;
	int ans = 0;
	
	REP(i, 0, n)
	{
		int k = 0;
		REP(j, 0, n)
		{
			if(i == j) continue;
			p[k].x = op[j].x - op[i].x;
			p[k].y = op[j].y - op[i].y;
			if(color[j]) p[k].x = -p[k].x, p[k].y = -p[k].y;
			p[k].rad = atan2(p[k].y, p[k].x);
			k++;
		}
		sort(p, p + k);
		
		int l = 0, r = 0, cnt = 2;
		while(l < k)
		{
			if(r == l) r = (r + 1) % k, cnt++;   //??????
			while(r != l && left(p[l], p[r])) r = (r + 1) % k, cnt++;
			cnt--;    //????????????
			l++;
			ans = max(ans, cnt);
		}
	}
	
	return ans;
}

int main()
{
	while(~scanf("%d", &n) && n)
	{
		REP(i, 0, n)
			scanf("%d%d%d", &op[i].x, &op[i].y, &color[i]);
		printf("%d
", solve());
	}
	return 0;	
}