这道题目用扫描法扫描法：在枚举的过程中维护一些重要的量， 从而简化计算这道题用到了极角， 叉积， 高一的我表示一脸懵逼

不过自己去百度了一下好像大概看得懂。这道题我还有一些疑问， 先这样吧

#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\n", solve());
	}
	return 0;	
} 

优质内容筛选与推荐>>
1、IE9快捷键大全
2、Python基础课程-Linux常用的命令行
3、DOM的概念及子节点类型【转】
4、5.2&5.3
5、Linux实战教学笔记48：openvpn架构实施方案（一）跨机房异地灾备

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中