[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]D Dendroctonus

    题目大意：给出一系列点，已知每个点是否被圆覆盖，询问是否能找到一个满足条件的圆（圆边界上的点既可算被覆盖，也可算不被覆盖），有输出“No”，没有输出“Yes”。

    题解：由于n<=100，可以直接枚举圆边界上的两个点或三个点，求出圆心与半径，然后O(n)判断其他点是否满足要求。注意特判n=0和n=1的情况。

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
const double eps=1e-8;

bool Get_Circle_Centre(int a0,int b0,int a1,int b1,int a2,int b2,double &a,double &b)
{
	int A0=2*(a1-a0);
	int B0=2*(b1-b0);
	int C0=a1*a1+b1*b1-a0*a0-b0*b0;
	int A1=2*(a2-a1);
	int B1=2*(b2-b1);
	int C1=a2*a2+b2*b2-a1*a1-b1*b1;
	if (A0*B1-A1*B0==0) return false;
	a=(double)(C0*B1-C1*B0)/(A0*B1-A1*B0);
	b=(double)(A0*C1-A1*C0)/(A0*B1-A1*B0);
	return true;
}

double Get_Dis2(double a0,double b0,double a1,double b1)
{
	return (a0-a1)*(a0-a1)+(b0-b1)*(b0-b1);
}

int x[maxn],y[maxn];
char ch[maxn];
int n;

int Check(double dis,double xc,double yc,double xn,double yn,char f)
{
	double nowdis=Get_Dis2(xn,yn,xc,yc);
	if (nowdis<dis+eps)
	{
		if ((!(fabs(nowdis-dis)<eps)) && f=='N') return 0;
	}
	else
	{
		if ((!(fabs(nowdis-dis)<eps)) && f=='I') return 0;
	}
	return 1;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d %c",&x[i],&y[i],&ch[i]);
	int cnt=0;
	for (int i=1;i<=n;i++) if (ch[i]=='I') cnt++;
	if (cnt<=1)
	{
		printf("No\n");
		return 0;
	}

	for (int i=1;i<=n;i++)
	for (int j=i+1;j<=n;j++)
	{
		int flg=1;
		double xc,yc;
		xc=(x[i]+x[j])/2.0,yc=(y[i]+y[j])/2.0;
		double dis2=Get_Dis2((double)x[i],(double)y[i],xc,yc);
		for (int l=1;l<=n && flg;l++)
			flg=Check(dis2,xc,yc,x[l],y[l],ch[l]);
		if (flg)
		{
			printf("No\n");
			return 0;
		}
	}
	for (int i=1;i<=n;i++)
	for (int j=i+1;j<=n;j++)
	for (int k=j+1;k<=n;k++)
	{
		int flg=1;
		double xc,yc;
		if (!Get_Circle_Centre(x[i],y[i],x[j],y[j],x[k],y[k],xc,yc)) continue;
		double dis2=Get_Dis2((double)x[i],(double)y[i],xc,yc);
		for (int l=1;l<=n && flg;l++)
			flg=Check(dis2,xc,yc,x[l],y[l],ch[l]);
		if (flg)
		{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

    另一种更优秀的做法是，枚举两个圆边界上的点，圆心一定在这两个点所连线段的中垂线上。为了满足其他的点的条件，每个点在中垂线上都有一个符合条件的区间，若所有区间交不为空则可以用一个圆覆盖。时间复杂度O(n^3)，不过我不会计算几何写不来...以后补。