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

Zarxdy34 posted @ 2017年10月11日 19:02 in Codeforces with tags 计算几何 , 36 阅读

    题目大意:给出一系列点,已知每个点是否被圆覆盖,询问是否能找到一个满足条件的圆(圆边界上的点既可算被覆盖,也可算不被覆盖),有输出“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),不过我不会计算几何写不来...以后补。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1