2017ICPC北京赛区网络赛 E Territorial Dispute(计算几何)

小鱼儿 2022-06-08 11:19 182阅读 0赞

**Territorial Dispute**

时间限制: 1000ms

单点时限: 1000ms

内存限制: 256MB

### 描述 ###

In 2333, the C++ Empire and the Java Republic become the most powerful country in the world. They compete with each other in the colonizing the Mars.

There are n colonies on the Mars, numbered from 1 to n. The i-th colony's location is given by a pair of integers (xi, yi). Notice that latest technology in 2333 finds out that the surface of Mars is a two-dimensional plane, and each colony can be regarded as a point on this plane. Each colony will be allocated to one of the two countries during the Mars Development Summit which will be held in the next month.

After all colonies are allocated, two countries must decide a border line. The Mars Development Convention of 2048 had declared that: A valid border line of two countries should be a straight line, which makes colonies of different countries be situated on different sides of the line.

The evil Python programmer, David, notices that there may exist a plan of allocating colonies, which makes the valid border line do not exist. According to human history, this will cause a territorial dispute, and eventually lead to war.

David wants to change the colony allocation plan secretly during the Mars Development Summit. Now he needs you to give him a specific plan of allocation which will cause a territorial dispute. He promises that he will give you 1000000007 bitcoins for the plan.

### 输入 ###

The first line of the input is an integer T, the number of the test cases (T ≤ 50).

For each test case, the first line contains one integer n (1 ≤ n ≤ 100), the number of colonies.

Then n lines follow. Each line contains two integers xi, yi (0 ≤ xi, yi ≤ 1000), meaning the location of the i-th colony. There are no two colonies share the same location.

There are no more than 10 test cases with n > 10.

### 输出 ###

For each test case, if there exists a plan of allocation meet David's demand, print "YES" (without quotation) in the first line, and in the next line, print a string consisting of English letters "A" and "B". The i-th character is "A" indicates that the i-th colony was allocated to C++ Empire, and "B" indicates the Java Republic.

If there are several possible solutions, you could print just one of them.

If there is no solution, print "NO".

### 注意 ###

This problem is special judged.

样例输入

2
    2
    0 0
    0 1
    4
    0 0
    0 1
    1 0
    1 1

样例输出

NO
    YES
    ABBA

**题意**：给你n个点，问你能否把这n个点分别标记为A，B，使得怎么样也无法用一条直线把A点和B点分在直线两侧，如果可以，就输出YES并按顺序输出这n个点分别标记为A还是B，不行就输出NO。

**思路**：这道题dalao说用凸包，但是我并没有用。首先根据题意显而易见的是n<=2的时候，都输出NO。然后当n=3的时候我们可以枚举这三个点，判断该点是否在另外两条线的连线上，简而言之就是看这三点共不共线，如果共线就输出YES，然后中间那个点输出B，两端的点输出A，反过来也行，如果不共线那么一定是NO。然后当n>=4的时候，我们可以发现一个规律，任意四个点一定存在满足条件的A和B的搭配，也就是说n>=4的时候一定输出YES，那么接下来就是看要如何搭配了，首先这四个肯定不是AAAA或者BBBB，那么我们先找三个A一个B的情况，这种情况其实只由一种，就是B在三个A所组成的三角形内部的时候，这个时候无论如何也不可能用一条线把A和B分成两部分，除此以外的情况都是可以的。然后就是两个A两个B的情况，这个时候我们只要看两个B的线段和两个A的线段是否相交即可，如果相交那么这四个点就是满足条件的点，最后按顺序输出即可，这四个点以外的点可以随便输出。三个B和一个A与三个A和一个B是一样的，不用考虑，这些结论都只要在纸上模拟一下便很快就可以知道。

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100000007;
    const int MOD = 1e9 + 7;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b){return b == 0 ? a : gcd(b, a%b);}
    
    struct POINT
    {
    	double x;
    	double y;
    	POINT(double a = 0, double b = 0) { x = a; y = b; } //constructor 
    };
    struct LINESEG
    {
    	POINT s;
    	POINT e;
    	LINESEG(POINT a, POINT b) { s = a; e = b; }
    	LINESEG() { }
    };
    
    POINT pp[105];
    
    double multiply(POINT sp, POINT ep, POINT op)
    {
    	return((sp.x - op.x)*(ep.y - op.y) - (ep.x - op.x)*(sp.y - op.y));
    }
    
    bool online(LINESEG l, POINT p)
    {
    	return((multiply(l.e, p, l.s) == 0) && (((p.x - l.s.x)*(p.x - l.e.x) <= 0) && ((p.y - l.s.y)*(p.y - l.e.y) <= 0)));
    }
    
    bool intersect(LINESEG u, LINESEG v)
    {
    	return((max(u.s.x, u.e.x) >= min(v.s.x, v.e.x)) && //排斥实验 
    		(max(v.s.x, v.e.x) >= min(u.s.x, u.e.x)) &&
    		(max(u.s.y, u.e.y) >= min(v.s.y, v.e.y)) &&
    		(max(v.s.y, v.e.y) >= min(u.s.y, u.e.y)) &&
    		(multiply(v.s, u.e, u.s)*multiply(u.e, v.e, u.s) >= 0) && //跨立实验 
    		(multiply(u.s, v.e, v.s)*multiply(v.e, u.e, v.s) >= 0));
    }
    
    bool InsideConvexPolygon(int vcount, POINT polygon[], POINT q) // 可用于三角形！ 
    {
    	POINT p;
    	LINESEG l;
    	int i;
    	p.x = 0; p.y = 0;
    	for (i = 0; i<vcount; i++) // 寻找一个肯定在多边形polygon内的点p：多边形顶点平均值 
    	{
    		p.x += polygon[i].x;
    		p.y += polygon[i].y;
    	}
    	p.x /= vcount;
    	p.y /= vcount;
    
    	for (i = 0; i<vcount; i++)
    	{
    		l.s = polygon[i]; l.e = polygon[(i + 1) % vcount];
    		if (multiply(p, l.e, l.s)*multiply(q, l.e, l.s)<0) /* 点p和点q在边l的两侧，说明点q肯定在多边形外 */
    			break;
    	}
    	return (i == vcount);
    }
    
    int main()
    {
    	POINT rec[3];
    	int T,n;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d", &n);
    		for (int i = 1; i <= n; i++)
    			scanf("%lf%lf", &pp[i].x, &pp[i].y);
    		if (n <= 2)
    			printf("NO\n");
    		else if (n == 3)
    		{
    			if (online(LINESEG(pp[2],pp[3]), pp[1]))//pp[1]是否在pp[2]和pp[3]的连线上，下同
    				printf("YES\nABB\n");
    			else if (online(LINESEG(pp[1],pp[3]), pp[2]))
    				printf("YES\nBAB\n");
    			else if (online(LINESEG(pp[1],pp[2]), pp[3]))
    				printf("YES\nBBA\n");
    			else
    				printf("NO\n");
    		}
    		else
    		{
    			if (intersect(LINESEG(pp[1], pp[2]), LINESEG(pp[3], pp[4])))//先找两A两B的情况，pp[1]和pp[2]的连线是否和pp[3]和pp[4]的连线相交，下同
    			{
    				printf("YES\nAABB");
    				for (int t = 5; t <= n; t++)
    					printf("A");
    				printf("\n");
    			}
    			else if (intersect(LINESEG(pp[1], pp[3]), LINESEG(pp[2], pp[4])))
    			{
    				printf("YES\nABAB");
    				for (int t = 5; t <= n; t++)
    					printf("A");
    				printf("\n");
    			}
    			else if (intersect(LINESEG(pp[1], pp[4]), LINESEG(pp[2], pp[3])))
    			{
    				printf("YES\nABBA");
    				for (int t = 5; t <= n; t++)
    					printf("A");
    				printf("\n");
    			}
    			else//当都不相交的时候来找三A一B的情况
    			{
    				rec[0] = pp[1],rec[1] = pp[2],rec[2] = pp[3];
    				if (InsideConvexPolygon(3, rec, pp[4]))//pp[4]是否在pp[1]pp[2]pp[3]组成的三角形中，下同
    				{
    					printf("YES\nAAAB");
    					for (int t = 5; t <= n; t++)
    						printf("A");
    					printf("\n");
    					continue;
    				}
    				rec[0] = pp[1],rec[1] = pp[2],rec[2] = pp[4];
    				if (InsideConvexPolygon(3, rec, pp[3]))
    				{
    					printf("YES\nAABA");
    					for (int t = 5; t <= n; t++)
    						printf("A");
    					printf("\n");
    					continue;
    				}
    				rec[0] = pp[1],rec[1] = pp[3],rec[2] = pp[4];
    				if (InsideConvexPolygon(3, rec, pp[2]))
    				{
    					printf("YES\nABAA");
    					for (int t = 5; t <= n; t++)
    						printf("A");
    					printf("\n");
    					continue;
    				}
    				rec[0] = pp[2],rec[1] = pp[3],rec[2] = pp[4];
    				if (InsideConvexPolygon(3, rec, pp[1]))
    				{
    					printf("YES\nBAAA");
    					for (int t = 5; t <= n; t++)
    						printf("A");
    					printf("\n");
    					continue;
    				}
    			}
    		}
    	}
    }