3172977_ac_46ms_164k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define MAXV 210

using namespace std;

struct point
{
	double x, y;
};

struct line
{
	point st, ed;
};

int n;
point p[MAXV];
line l[MAXV>>1];

bool equal(point a,point b)
{
	if(a.x!=b.x||a.y!=b.y)
		return false;
	return true;
}

double cross(point a,point b,point c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

void solve()
{
	int i, j, k;

	if(n < 3)
	{
		puts("Yes!");
		return ;
	}
	bool fail;
	for(i = 0; i < n*2; i++)
	{
		for(j = i+1; j < n*2; j++)
		{
			if(!equal(p[i],p[j]))
			{
				fail = false;
				for(k = 0; k < n; k++)
				{
					double v1 = cross(l[k].st,p[j],p[i]);
					double v2 = cross(l[k].ed,p[j],p[i]);
					if(v1 * v2 > 0)
					{
						fail = true;
						break;
					}
				}
				if(!fail)
				{
					puts("Yes!");
					return ;
				}
			}
		}
	}
	puts("No!");
}

int main()
{
	int i, cas;

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%d",&n);
		for(i = 0; i < n; i++)
		{
			scanf("%lf%lf%lf%lf",&l[i].st.x,&l[i].st.y,&l[i].ed.x,&l[i].ed.y);
			p[i] = l[i].st;
			p[i+n] = l[i].ed;
		}
		solve();
	}
	return 0;
}