HDU 4033

无数次WA之后,摸索出正确的思路了。

开始是二分边长,然后通过正玄定理和余玄定理求面积,但是不行。

然后通过图形旋转,合并,求面积,逆推边长,也不行。但值得一提的是,这个办法后来测试时发现,是判断不可能情况的时候有问题,所以才WA的。

最后的做法是,二分边长,然后通过边对的中心夹角和是否为360度来判断,推倒重写,啪啪地写了20分钟,AC了。

#include <cstdio>
#include <cmath>

double abs(double x){
	if(x<0)return -x;
	return x;
}

int main(){
	int cs,ts,n,i;
	double ag,l[105],l2[105],left,right,mid;
	const double pi=acos(-1.0);
	scanf("%d",&ts);
	for(cs=1;cs<=ts;cs++){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%lf",&l[i]);
			l2[i]=l[i]*l[i];
		}
		left=abs(l[0]-l[n-1]);//大于所有两边的差
		right=l[0]+l[n-1];//小于所有两边的和
		for(i=1;i<n;i++){
			if(left<abs(l[i]-l[i-1]))left=abs(l[i]-l[i-1]);
			if(right>l[i]+l[i-1])right=l[i]+l[i-1];
		}
		if(left>right){
			printf("Case %d: impossiblen",cs);
		}else{
			while(right-left>0.0000001){
				mid=(right+left)/2.0;
				ag=acos((l2[0]+l2[n-1]-mid*mid)/(2.0*l[0]*l[n-1]));
				for(i=1;i<n;i++)
					ag+=acos((l2[i]+l2[i-1]-mid*mid)/(2.0*l[i]*l[i-1]));
				if(ag>2*pi){
					right=mid;
				}else{
					left=mid;
				}
			}
			if(abs(ag-2*pi)>0.00001)
				printf("Case %d: impossiblen",cs);
			else
				printf("Case %d: %.3fn",cs,mid);
		}
	}
	return 0;
}

最后给出求面积,逆推边长的办法,不过判断不可能的办法,用的是上面的办法,其实,算是多求了。

#include <cstdio>
#include <cmath>
#include<cstring>
const double pi=acos(-1.0);
double a,ag,l[105],l2[105],left,right,mid;
int n;

double abs(double x){
	if(x<0)return -x;
	return x;
}
double hellen(double a,double b,double c){
	double p=(a+b+c)/2.0;
	return sqrt(p*(p-a)*(p-c)*(p-b));
}

void gao(){
	double vi=pi-2*pi/n,si=sin(vi),co=cos(vi);
	int i;
	double s=0.5*l2[0]*si+hellen(sqrt(2.0*l2[0]*(1-co)),l[1],l[n-1]);
	s+=0.5*l2[n-1]*si+hellen(sqrt(2.0*l2[n-1]*(1-co)),l[0],l[n-2]);
	for(i=1;i<n-1;i++){
		s+=0.5*l2[i]*si+hellen(sqrt(2.0*l2[i]*(1-co)),l[i+1],l[i-1]);
	}
	s/=2.0;
	a=sqrt(s*4*tan(pi/n)/n);
}

int main(){
	int cs,ts,i;
	scanf("%d",&ts);
	for(cs=1;cs<=ts;cs++){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%lf",&l[i]);
			l2[i]=l[i]*l[i];
		}
		left=abs(l[0]-l[n-1]);//大于所有两边的差
		right=l[0]+l[n-1];//小于所有两边的和
		for(i=1;i<n;i++){
			if(left<abs(l[i]-l[i-1]))left=abs(l[i]-l[i-1]);
			if(right>l[i]+l[i-1])right=l[i]+l[i-1];
		}
		if(left>right){
			printf("Case %d: impossiblen",cs);
		}else{
			while(right-left>0.0000001){
				mid=(right+left)/2.0;
				ag=acos((l2[0]+l2[n-1]-mid*mid)/(2.0*l[0]*l[n-1]));
				for(i=1;i<n;i++)
					ag+=acos((l2[i]+l2[i-1]-mid*mid)/(2.0*l[i]*l[i-1]));
				if(ag>2*pi){
					right=mid;
				}else{
					left=mid;
				}
			}
			if(abs(ag-2*pi)>0.00001)
				printf("Case %d: impossiblen",cs);
			else{
		//		printf("Case %d: %.3fn",cs,mid);
				gao();
				printf("Case %d: %.3fn",cs,a);
			}
		}
	}
	return 0;
}

HDU 4034

弗洛伊德的理解吧。

如果能够从某一条边中转使边长短了,也就是有松弛操作,那就是impossible。

如果一条边等于另外两条边的和,也就是说,这条边可以通过别的边组合而成,也就是多余的,减去,不过我代码是加上的,也就是负逻辑。

#include <cstdio>

int mp[105][105],n;

int main(){
	int ts,cs,i,j,k,ans;
	bool fg;
	scanf("%d",&ts);
	for(cs=1;cs<=ts;cs++){
		scanf("%d",&n);
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				scanf("%d",&mp[i][j]);
		fg=false;
		ans=0;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(i==j)continue;
				for(k=0;k<n;k++){
					if(i==k||j==k)continue;
					if(mp[i][j]>mp[i][k]+mp[k][j]){
						fg=true;
						goto E;
					}
					if(mp[i][j]==mp[i][k]+mp[k][j])goto EE;
				}
				ans++;
EE:;
			}
		}
E:
		printf("Case %d: ",cs);
		if(fg){
			printf("impossiblen");
		}else{
			printf("%dn",ans);
		}
	}
	return 0;
}