首页 > ACM题库 > HDU-杭电 > HDU 4736-This Is The Job The Bear Finds[解题报告]HOJ
2015
09-17

HDU 4736-This Is The Job The Bear Finds[解题报告]HOJ

This Is The Job The Bear Finds

问题描述 :

This is the job the bear finds
This is the job the bear finds
This is the job the bear finds
Not with a code but a brick.

                                                  - Kenneth Snow, The Hollow Bear

Bearchild is working in a construction team. Life is hard, and his job is just carrying bricks from here to there, what a waste of time! So, our lovely Bearchild has invented a strange machine to help him.
The machine consists three parts: A rope, a little, round pulley (regarded as points) and a big pulley which is a convex hull (Bearchild is short of money and can’t make his big pulley round!).
One end of the rope is fixed with bricks, the rope goes around the small pulley, and finally connects the big pulley on its contour. It’s guaranteed that the small pulley is located to the left of the big one.
You can see that when the big pulley spins clockwise around its center of gravity, the bricks will be pulled up, and finally reach the small pulley as the destination. Note that the rope will circle around the contour of the big pulley as it spins.
See the picture for more information, there will be no collision when spinning.

Little Wish~ lyrical step~

In this problem, first of all we let the pulley spin for one or more circles so the rope becomes tight.
After that, the positions of the two pulleys are given. Then you have to deal a lot of queries, for each query, the distance from the bricks and the small pulley (also as the destination) is given.
Your task is to calculate the degree the pulley has yet to spin to pull the bricks to the destination.

输入:

The first line has a number T (T <= 1000) , indicating the number of test cases.
For each test case, first line is a number n, which is the number of points of the big pulley (As a convex hull). Then n lines follow, each with two numbers as the x and y coordinate of each point.
Those points are given in counter-clockwise order. Then a line with two numbers, which are the x and y coordinate of the small pulley. Those coordinates are in the range [-1000000, 1000000].
Then a number m indicating the number of queries.
For next q lines, each contains a number l (0 < l < 109), which is the distance between the bricks and the small pulley.
For 90% of the data, we have n,m <= 100, All the data have n <= 104, m <= 105, and all the numbers in the input are integers.

输出:

The first line has a number T (T <= 1000) , indicating the number of test cases.
For each test case, first line is a number n, which is the number of points of the big pulley (As a convex hull). Then n lines follow, each with two numbers as the x and y coordinate of each point.
Those points are given in counter-clockwise order. Then a line with two numbers, which are the x and y coordinate of the small pulley. Those coordinates are in the range [-1000000, 1000000].
Then a number m indicating the number of queries.
For next q lines, each contains a number l (0 < l < 109), which is the distance between the bricks and the small pulley.
For 90% of the data, we have n,m <= 100, All the data have n <= 104, m <= 105, and all the numbers in the input are integers.

样例输入:

2
4
0 0
1 0
1 1
0 1
-1 2
2
1
4
3
0 0
1 1
-1 1
-2 1
3
1
2
3

样例输出:

Case #1:
90.000
360.000
Case #2:
64.413
140.446
233.660

// Time 1718 ms; Memory 1500 K
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define eps 1e-10
#define sqr(a) ((a)*(a))
#define pi (2.0*asin(1.0))

using namespace std;

double ma[100010];

int sig(double a)
{
	return (a>eps)-(a<-eps);
}

typedef struct point
{
	double x,y;
	point(double xx=0,double yy=0):x(xx),y(yy){}
}vector;

struct node
{
	double ang,d;
	point c;
}th[10010];

point pt[10010];

bool operator < (point a,point b)
{
	return a.x<b.x || (a.x==b.x && a.y<b.y);
}
vector operator - (point a,point b)
{
	return vector(a.x-b.x,a.y-b.y);
}
point operator + (point a,vector b)
{
	return point(a.x+b.x,a.y+b.y);
}
vector operator * (vector a,double b)
{
	return vector(a.x*b,a.y*b);
}
vector operator / (vector a,double b)
{
	return vector(a.x/b,a.y/b);
}
double dot(vector a,vector b)
{
	return a.x*b.x+a.y*b.y;
}
double cross(vector a,vector b)
{
	return a.x*b.y-a.y*b.x;
}
double len(vector a)
{
	return sqrt(sqr(a.x)+sqr(a.y));
}
double angle(vector a,vector b)
{
	double d=dot(a,b)/len(a)/len(b);
	if(sig(d-1)==0) return 0;
	if(sig(d+1)==0) return pi;
	return acos(d);
}
double dis(point a,point b,point p)
{
	return fabs(cross(b-a,p-a))/len(b-a);
}
vector rot(vector a,double b)
{
	double s=sin(b),c=cos(b);
	return vector(a.x*c-a.y*s,a.x*s+a.y*c);
}
vector rsize(vector a,double b)
{
	b/=len(a);
	return vector(a.x*b,a.y*b);
}
point bcenter(int n,double &l)
{
	point p,s;
	double tp,area=0,tpx=0,tpy=0;
	point t1=pt[0],t2=pt[0];
	p=pt[0];
	l=0;
	for(int i=1;i<=n;i++)
	{
		s.x=pt[i==n ? 0 : i].x;
		s.y=pt[i==n ? 0 : i].y;
		if(s<t1) t1=s;
		else if(t2<s) t2=s;
		l+=len(pt[i-1]-s);
		tp=cross(p,s);area+=tp/2;
		tpx+=(p.x+s.x)*tp;tpy+=(p.y+s.y)*tp;
		p.x=s.x;p.y=s.y;
	}
	if(sig(area)==0) s=(t1+t2)/2;
	else 
	{
		s.x=tpx/(6*area);s.y=tpy/(6*area);
	}
	return s;
}
point getp(point p,vector v,point cp,double r)
{
	double a=v.x,b=p.x-cp.x,c=v.y,d=p.y-cp.y;
	double e=sqr(a)+sqr(c),f=2*(a*b+c*d),g=sqr(b)+sqr(d)-sqr(r);
	double del=sqr(f)-4*e*g;
	double t=(-f+sqrt(del))/(2*e);
	return p+v*t;
}

int main()
{
	int i,j,k,u,t,n,m,cnt,my,cas=1;
	double l,sl,rad,lp,lq,ang1,ang2,ds,ll;
	point ct,ct1,ct2,g;
	vector v,w;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		my=0;
		for(i=0;i<n;i++)
		{
			scanf("%lf%lf",&pt[i].x,&pt[i].y);
			if(sig(pt[my].x-pt[i].x)>0) my=i;
		}
		scanf("%lf%lf%d",&ct.x,&ct.y,&m);
		while(sig(cross(pt[my]-ct,pt[(my-1+n)%n]-pt[my]))>0) my=(my-1+n)%n;
		g=bcenter(n,sl);                 
		v=ct-g;
		ll=len(v);
		ct1=ct;
		th[0].c=ct;
		for(j=my,k=0;k<n;k++)
		{
			u=(j+k)%n;
			lp=len(pt[u]-ct1);
			ct2=getp(pt[u],pt[(u+1)%n]-pt[u],g,ll);
			th[k+1].ang=th[k].ang+angle(ct1-g,ct2-g);      
			th[k+1].d=th[k].d+len(pt[u]-ct2)-lp;         
			th[k+1].c=ct2;
			ct1=ct2;
		}
		for(i=0;i<m;i++)
		{
			scanf("%lf",&l);
			cnt=(int)l/sl;
			l=l-cnt*sl;
			rad=cnt*2*pi;
			int right=n,left=1,mid=(n+1)/2;
			double tmp1,tmp2;
			while(left<=right)
			{
				tmp1=l-th[mid].d;
				tmp2=l-th[mid-1].d; 
				if(sig(tmp1)==0) 
				{
					mid++;break;
				}
				if(sig(tmp2)==0) break;
				if(sig(tmp1)<0 && sig(tmp2)>0) 
					break;
				if(sig(tmp1)>0) left=mid+1;
				else right=mid-1;
				mid=(left+right)/2;
			}
			j=mid;   
			if(left>right) j++;
			rad+=th[j-1].ang;
			l-=th[j-1].d;        
			if(sig(l)>0)
			{
				u=(my+j-1)%n;
				lp=len(pt[u]-g);
				lq=len(th[j-1].c-pt[u])+l;
				ang1=acos((sqr(lp)+sqr(ll)-sqr(lq))/(2*lp*ll));
				ang2=ang1-angle(pt[u]-g,th[j-1].c-g);
				rad+=ang2;          
			}
			ma[i]=rad/pi*180;
		}
		printf("Case #%d:\n",cas++);
		for(i=0;i<m;i++) 
			printf("%.3lf\n",ma[i]);
	}
	return 0;
}

参考:http://www.cnblogs.com/keanuyaoo/archive/2013/09/15/3322863.html