nyoj 1099 Lan Xiang's Square (水題)

Lan Xiang's Square

描述

Excavator technology which is strong, fast to Shandong to find Lan Xiang.

Then the question comes.. :)

for this problem , i will give you four points. you just judge if they can form a square.

if they can, print "Yes", else print "No".

Easy ? just AC it.

ACM_張開創

題意：給出四個點坐標，判斷是否能組成正方形。

證明：四條邊相等，並且有一個角是直角 為正方形。

題很簡單 ，自己的思路也一直整錯 可就是wa

可能數據太給力了，調試n次，發現sqrt()導致精度損失。 這個錯誤可真難找。。。

先貼上wa的代碼

 

 
#include 
#include 
#define inf 500000005
int main()
{
	double a[4],b[4],x1,x2,x3,x4,y1,y2,y3,y4;
	double sum1,sum2,l1,l2,l3,l4,l;
	int i,t;
	scanf("%d",&t);
	while(t--)
	{
		sum1=sum2=0,x1=x2=x3=x4=y1=y2=y3=y4=inf;
		for(i=0;i<4;i++)
			scanf("%lf %lf",&a[i],&b[i]),sum1+=a[i],sum2+=b[i];
		sum1=sum1/4,sum2=sum2/4;
		for(i=0;i<4;i++)
		{
			if(a[i]=sum2)
				x1=a[i],y1=b[i];
			if(a[i]<=sum1&&b[i]=sum1&&b[i]>sum2)
				x3=a[i],y3=b[i];
			if(a[i]>sum1&&b[i]<=sum2)
				x4=a[i],y4=b[i];
		}
		if(x1==inf||x2==inf||x3==inf||x4==inf||y1==inf||y2==inf||y3==inf||y4==inf)
		{
			printf("No\n");
			continue;
		}
		l1=sqrt(pow(y1-y2,2)+pow(x1-x2,2));
		l2=sqrt(pow(y2-y4,2)+pow(x2-x4,2));
		l3=sqrt(pow(y3-y4,2)+pow(x3-x4,2));
		l4=sqrt(pow(y1-y3,2)+pow(x1-x3,2));
		l=sqrt(pow(y3-y2,2)+pow(x3-x2,2));
		if(l1==l2&&l1==l3&&l1==l4&&fabs(l1*l1+l4*l4-l*l)<0.00001)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}                

 

 

#include 
#include 
#define inf 500000005
int main()
{
	double a[4],b[4],x1,x2,x3,x4,y1,y2,y3,y4;
	double sum1,sum2,l1,l2,l3,l4,l;//l1,l2,l3,l4,l分別表示四條邊和一個對角線。
	int i,t;
	scanf("%d",&t);
	while(t--)
	{
		sum1=sum2=0,x1=x2=x3=x4=y1=y2=y3=y4=inf;//初始坐標
		for(i=0;i<4;i++)
			scanf("%lf %lf",&a[i],&b[i]),sum1+=a[i],sum2+=b[i];
		sum1=sum1/4,sum2=sum2/4;
		for(i=0;i<4;i++)//更新坐標
		{
			if(a[i]=sum2)
				x1=a[i],y1=b[i];
			if(a[i]<=sum1&&b[i]=sum1&&b[i]>sum2)
				x3=a[i],y3=b[i];
			if(a[i]>sum1&&b[i]<=sum2)
				x4=a[i],y4=b[i];
		}
		if(x1==inf||x2==inf||x3==inf||x4==inf||y1==inf||y2==inf||y3==inf||y4==inf)//如果有一個坐標未更新 ，no
		{
			printf("No\n");
			continue;
		}
		l1=pow(y1-y2,2)+pow(x1-x2,2);//和wa不同的地方
		l2=sqrt(pow(y2-y4,2)+pow(x2-x4,2));
		l3=sqrt(pow(y3-y4,2)+pow(x3-x4,2));
		l4=pow(y1-y3,2)+pow(x1-x3,2);//同上
		l=pow(y3-y2,2)+pow(x3-x2,2);//同上
		if(sqrt(l1)==l2&&sqrt(l1)==l3&&sqrt(l1)==sqrt(l4)&&l1+l4==l)
			printf("Yes\n");
		else 
			printf("No\n");
	}
	return 0;
}        

 

輸入

T <= 105 cases.
for every case
four points, and every point is a grid point .-10^8 <= all interger <= 10^8。
grid point is both x and y are interger.

輸出

Yes or No

樣例輸入

1
1 1
-1 1
-1 -1
1 -1

樣例輸出

Yes

提示

you think this is a easy problem ? you dare submit, i promise you get a WA. :)

來源

myself

上傳者
ac代碼