pku1228.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <algorithm>
#define size 1001
using namespace std;
typedef struct 
{
	int x, y;
} Node;
Node p[size];

int Abs(int x)
{
	return x > 0 ? x : -x;
}

int Dis(Node a, Node b)
{
	return Abs(a.x - b.x) + Abs(a.y - b.y);
}

int det(int x1, int y1, int x2, int y2)
{
	return x1 * y2 - x2 * y1;
}

int cross(Node a, Node b, Node c)
{
	return det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

bool cp1(Node a, Node b)
{
	int ans = cross(p[0], a, b);
	return ans > 0 || (ans == 0 && Dis(p[0], a) > Dis(p[0], b));
}

bool Solve()
{
	int N, i, id, s, cnt;
	Node tmp;
	id = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &p[i].x, &p[i].y);
		if (p[i].x < p[id].x || (p[i].x == p[id].x && p[i].y < p[id].y))
		{
			id = i;
		}
	}
	if (N <= 2)
	{
		return 0;
	}
	tmp = p[id];
	p[id] = p[0];
	p[0] = tmp;
	sort(p + 1, p + N, cp1);

	if (cross(p[0], p[1], p[N - 1]) == 0)
		return 0;

	for (i = 1; i < N; i++)
	{
		if (cross(p[0], p[1], p[i]) != 0)
		{
			break;
		}
	}
	i--;
	tmp = p[1];
	p[1] = p[i];
	p[i] = tmp;
	p[N] = p[0];
	s = 0;
	cnt = 2;
 
	for (i = 2; i <= N; i++)
	{
		if (cross(p[s], p[i - 1], p[i]) == 0)
		{
			cnt++;
		}
		else
		{
			if (cnt < 3)
			{
				return 0;
			}
			else
			{
				s = i - 1;
				cnt = 2;
			}
		}
	}
	if (cnt < 3)
	{
		return 0;
	}
	return 1;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		if (Solve())
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}