2705941_ce.c

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

//  [9/24/2007 Administrator]
//  PKU 3384
#include <stdio.h>
#include <math.h>
#define PI 4.0*atan(1)

int n, r;
int pot[101][2];

int input()
{
	int i;

	if(scanf("%d%d",&n,&r)!=2)
		return 0;
	for (i = 0; i < n; i++)
		scanf("%d%d",&pot[i][0],&pot[i][1]);
	return 1;
}

void cal(int i, double &X, double &Y)
{
	int a, b;
	double x1, y1, x2, y2, x3, y3;
	double A1, B1, C1, A2, B2, C2;
	double S1, S2;

	a = i - 1;b = i + 1;
	if (a < 0)	a = n-1;
	if (b == n)	b = 0;
	x1 = pot[i][0];y1 = pot[i][1];
	x2 = pot[a][0];y2 = pot[a][1];
	x3 = pot[b][0];y3 = pot[b][1];
	A1 = y1-y2;B1 = x2-x1;C1 = x1*y2-x2*y1;
	A2 = y1-y3;B2 = x3-x1;C2 = x1*y3-x3*y1;
	if (A1*x3+B1*y3+C1<0)
		A1 *= -1,B1 *= -1,C1 *= -1;
	if (A2*x2+B2*y2+C2<0)
		A2 *= -1,B2 *= -1,C2 *= -1;
	S1 = sqrt(A1*A1+B1*B1);S2 = sqrt(A2*A2+B2*B2);
	Y = (r*(A2*S1-A1*S2)+C2*A1-C1*A2)/(A2*B1-A1*B2);
	X = (r*(B2*S1-B1*S2)+C2*B1-C1*B2)/(B2*A1-B1*A2);
}

double dis(double aa,double bb,int i)
{
	double x1, y1, x2, y2;
	double A, B, C;

	x1 = pot[i][0];y1 = pot[i][1];
	i++;
	if(i==n)	i = 0;
	x2 = pot[i][0];y2 = pot[i][1];
	A = y1-y2;B = x2-x1;C = x1*y2-x2*y1;
	return fabs(aa*A+bb*B+C)/(sqrt(A*A+B*B));
}
 
int check(double a,double b)
{
	int i;

	for (i = 0; i < n; i++)
	{
		if (dis(a,b,i)-r<0)
			return 1;
	}
	return 0;
}

double area(double xi,double yi,double xj,double yj)
{
	return sqrt((xi-xj)*(xi-xj)+(yi-yj)*(yi-yj));
}

void solve()
{
	int i, j;
	double xi, yi, xj, yj;
	double max = -1, tmp;
	double x1, y1, x2, y2;

	for (i = 0; i < n; i++)
	{
		cal(i,xi,yi);
		if(check(xi,yi))
			continue;
		for (j = i; j < n; j++)
		{
			cal(j,xj,yj);
			if(check(xj,yj))
				continue;
			if ((tmp=area(xi,yi,xj,yj))>max)
			{
				max = tmp;
				x1 = xi;x2 = xj;
				y1 = xj;y2 = yj;
			}
		}
	}
	printf("%.4lf %.4lf %.4lf %.4lf\n",x1,y1,x2,y2);
}

int main()
{
	while (input())
		solve();
	return 0;
}