首页 > ACM题库 > HDU-杭电 > HDU 4058-Advanture of Xiaoxingxing-计算几何-[解题报告]HOJ
2015
04-16

HDU 4058-Advanture of Xiaoxingxing-计算几何-[解题报告]HOJ

Advanture of Xiaoxingxing

问题描述 :

Fat Xiaoxingxing was so fat that he couldn’t walk with his feet. But he didn’t care about it. "Sphere is also a shape of body." He always said and somehow he was a bit happy with that.

The only thing he cared was his Lost Piece (LP). He was born with some imperfection. He felt depressed with that. Not does he become complete until he could find his LP. "I will find my LP." As he declared, he set off for his LP. He couldn’t walk, so he could only move by rolling. He had to bear the hard sunshine or the heavy rain. However, he still sang songs on his way, "La… la… la… I am going to find my LP…" After a long journey of adventure, he found where his LP lay. It was not far away from him.

Now given the positions of Xiaoxingxing and his LP, you are asked to calculate the minimum degree he needed to roll to reach his LP.

输入:

There are multiple test cases. The first line contains an integer n (0 < n ≤ 100). The body of Xiaoxingxing can be decribed as a polygon of n points. Each of the following n lines contains two integers xi and yi (|xi| ≤ 10000, 0 ≤ yi ≤ 10000) , descibing a point of the polygon clockwise or counter-clockwise. The first point of the polygon is always the origin and the polygon will not be self-crossed. The last line of each test case contains two integers X and Y (xi < X ≤ 10000, 0 ≤ Y ≤ 10000), descrbing the position of the Lost Piece. Xiaoxingxing can only roll with some point fixed on the ground where y = 0.

输出:

There are multiple test cases. The first line contains an integer n (0 < n ≤ 100). The body of Xiaoxingxing can be decribed as a polygon of n points. Each of the following n lines contains two integers xi and yi (|xi| ≤ 10000, 0 ≤ yi ≤ 10000) , descibing a point of the polygon clockwise or counter-clockwise. The first point of the polygon is always the origin and the polygon will not be self-crossed. The last line of each test case contains two integers X and Y (xi < X ≤ 10000, 0 ≤ Y ≤ 10000), descrbing the position of the Lost Piece. Xiaoxingxing can only roll with some point fixed on the ground where y = 0.

样例输入:

4
0 0
0 1
-1 1
-1 0
1 0
4
0 0
0 3
-4 3
-4 0
3 6

样例输出:

Case 1: 90.00
Case 2: Impossible

随机整了10000组数据,跟岛娘的结果90%相似了,但还是WA中。。。

希望明天能过了吧,先回寝室洗洗睡了。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#define PA system("pause");
#define X 110
#define eps 1e-8
#define pi 3.14159265358979323
using namespace std;
struct point{
	double x,y;
}p[X],q[X],stk[X];
point yd,x100,A,B;
int top,n;
double minjiao;
double max(double x,double y){return x>y+eps?x:y;}
double min(double x,double y){return x<y-eps?x:y;}
double dis(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cp(point a,point b,point c){
	double t=(c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
	if(t<-eps)return -1;
	if(t>eps)return 1;
	return 0;
}
int cmp(point a,point b){
	if(cp(stk[0],a,b)==0)
	    return dis(stk[0],a)<dis(stk[0],b);
	return cp(stk[0],a,b)<0;
}
void graham(){
	int i;
	top=1;
	sort(stk+1,stk+n,cmp);
	p[0]=stk[0];p[1]=stk[1];
	for(i=2;i<n;i++){
		while(cp(p[top],p[top-1],stk[i])<=0&&top)top--;
		p[++top]=stk[i];
	}
	p[++top]=stk[0];
}
point rorate(point b,double ang){
	point c;
	c.x=b.x*cos(ang)-b.y*sin(ang);
	c.y=b.x*sin(ang)+b.y*cos(ang);
	return c;
}
double qiujiao(point e){
	if(fabs(e.y)<eps&&e.x>eps)return 0;
	if(fabs(e.y)<eps&&e.x<-eps)return pi;
	double a=dis(e,yd),b=dis(e,x100);
	return acos((a*a+1e4-b*b)/(200*a));
}
int pointin(point a,point s[],int n){
	int i;s[n]=s[0];s[n+1]=s[1];
	for(i=0;i<n-1;i++)
	    if(cp(s[i],s[i+1],a)*cp(s[i+1],s[i+2],a)<0)
	        return 0;
	return 1;
}
int bi(point a,point b,point A,double ang){
	if(cp(a,b,A)<0)swap(a,b);
	double l=0,r=ang,md;
	point c;
	while(l<r-eps){
		md=(l+r)/2;
		c=rorate(A,md);
		if(cp(a,b,c)<0)
		    r=md;
		else
		    l=md;
	}
	printf("%lf,%lf\n",c.x,c.y);
	if(c.x>min(a.x,b.x)&&c.x<max(a.x,b.x)&&
	c.y>min(a.y,b.y)&&c.y<max(a.y,b.y)){
	    md=qiujiao(c)-qiujiao(A);
	    minjiao=minjiao<md?minjiao:md;
	    return 1;
	}
	return 0;
}
int main(){
	yd.x=yd.y=x100.y=0;x100.x=100;
	int i,j,flag,cs=1;
	double as,sum,jiaoA,jiaoP,lenA;
	freopen("in2.txt","r", stdin);
	freopen("out.txt","w",stdout);
	while(~scanf("%d",&n)){
		for(i=0;i<n;i++){
		    scanf("%lf%lf",&stk[i].x,&stk[i].y);
		    q[i]=stk[i];
		}
		scanf("%lf%lf",&A.x,&A.y);
		if(cp(q[0],q[1],q[2])>0)
		    for(i=1;i<n/2;i++)
		        swap(q[i],q[n-i]);
		graham();
		q[n]=q[0];
		as=0;sum=0;minjiao=5;
		for(i=0;i<top;i++)sum+=dis(p[i],p[i+1]);
		if(A.x>sum){
			A.x=fmod(A.x,sum);
			as=(int)(A.x/sum);
			as*=2*pi;
			if(pointin(A,p,top)){
				as-=2*pi;A.x+=sum;
			}
		}
		for(j=0,flag=0;j<=2*top&&!flag;j++){
        for(i=0;i<=n;i++)
		    printf("%.2lf,",q[i].x);puts("");puts("");
        for(i=0;i<=n;i++)
		    printf("%.2lf,",q[i].y);puts("");puts("");
			jiaoA=qiujiao(A);
			jiaoP=qiujiao(p[1]);
			B=rorate(A,jiaoP);
			lenA=sqrt(A.x*A.x+A.y*A.y);
			for(i=0;i<n;i++){
                printf("x=%lf y=%lf x=%lf y=%lf\n\n",q[i].x,q[i].y,q[i+1].x,q[i+1].y);
                printf("len1=%lf len2=%lf\n",dis(q[i],yd),dis(q[i+1],yd));
                printf("cp1=%d,cp2=%d\n",cp(q[i],q[i+1],A),cp(q[i],q[i+1],B));
                printf("Ax=%lf Ay=%lf Bx=%lf By=%lf\n",A.x,A.y,B.x,B.y);
			    if((dis(q[i],yd)>=lenA||dis(q[i+1],yd)>=lenA)&&
		            cp(q[i],q[i+1],A)*cp(q[i],q[i+1],B)<=0)
						if(bi(q[i],q[i+1],A,jiaoP))
						flag=1;
					}
			if(!flag){
				for(i=0;i<=top;i++)
				    p[i]=rorate(p[i],-jiaoP);
				for(i=0;i<=n;i++)
				    q[i]=rorate(q[i],-jiaoP);
				for(i=0;i<=top;i++)
				    if(i!=1)p[i].x-=p[1].x;
				for(i=0;i<=n;i++)
				    q[i].x-=p[1].x;
				A.x-=p[1].x;
				p[1].x=p[1].y=0;
				for(i=1;i<=top;i++)
				    p[i-1]=p[i];
				for(i=1;i<=n;i++)
				    q[i-1]=q[i];
				p[top]=p[0];q[n]=q[0];
				as+=jiaoP;
			}
			else
			    as+=minjiao;
		}
		printf("Case %d: ",cs++);
		if(flag)printf("%.2lf\n",as*180/pi);
		else printf("Impossible\n");
	}
	return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zzxyyx_1/article/details/8091477


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.