ZOJ 1018 Deformed Wheel

Deformed Wheel

Time Limit: 2000 msMemory Limit: 65536 KB

The village's carpentry is located by a hill side. The carpenter's two little boys play with a piece of wood which looks like a deformed wheel with two identical convex polygon-shaped faces. One boy sets the wooden wheel on a slope at the hill top and let it roll down. The other boy is to quickly place himself at where he guesses the rolling wood would stop. Your program is to help him make the right guess.

More formally, we consider the wooden wheel as a simple convex polygon and we approximate the hill by a sequence of connected line segments with decreasing slopes. The slope of the last segment in the sequence is assumed to be zero, and the slope of the first segment is assumed to be a positive number. Initially, the wheel is placed on the hill such that there is at least one point of contact between the wheel and segments. For example in the following figure, the wheel in its initial position is drawn in solid lines, while the final position is drawn in dashed lines.

At any instant, the wheel rotates around one of its vertices, say P, if the y-coordinate of its center of gravity is decreased (note that this condition is necessary at any instant during the motion). It can be easily shown that at any instant, there is at most one such vertex. Rotation around P is stopped when the wheel touches a segment. The motion continues until no vertex can be found such that the wheel can rotate around it. At any instant, assume that changing the position of the center of gravity in any direction for at most 10-5 units, does not affect the stability of the wheel. Also assume that the friction between the wheel and the surface of the hill is so high that the wheel never slides on the surface.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. In the first line of each test case there is an integer n (1 <= n <= 10), that indicates the number of the wheel vertices. In each of the next n lines, there is a pair of numbers which are x and y coordinates of the initial position of a vertex. After this, there is a single line containing the initial x and y coordinates of the center of gravity of the wheel. You can assume that the center of gravity is inside or on the boundary of the polygon (note that the given center of gravity is not necessarily computable from wheel's geometric shape). Next lines of the test data will describe the shape of the hill. The surface of the hill is approximated with a series of line segments with decreasing slopes ending with a horizontal line segment. For each segment, there is a line containing length and slope of a segment (both of them are real numbers). The lines are ordered in decreasing slope (The last line of this part of the input has slope zero). You can assume that the last (horizontal) line is long enough that the wheel would not pass its end. In the last line of the test case, there is a line containing the x and y coordinates of the right end-point of the first segment. All coordinates and slopes are real numbers.

Output

For each test case, there should be a single line in the output, containing two numbers which are x and y coordinates of the wheel's center of gravity. Round the numbers in the output to 3 digits after decimal point.

Sample Input

1
4
40 30
30 37
24 30
30 26
27 29
30 1
100 0
40 30

Sample Output

28.854 20.031

变形轮

村庄的木匠铺坐落在山坡上。木匠的两个小男孩在玩一块木头，这块木头看起来像一个变形的轮子，有两个相同的凸多边形面。一个男孩把木轮子放在山顶的斜坡上，让它滚下来。另一个男孩迅速地站在他认为滚动的木头会停止的地方。你的计划是帮助他做出正确的猜测。

更正式地说，我们把木轮看作是一个简单的凸多边形，我们通过一系列斜坡递减的连接线段来近似小山。假设序列中最后一段的斜率为零，第一段的斜率为正数。最初，所述车轮被放置在所述山丘上，使所述车轮和部分之间至少有一个接触点。例如在下面的图中，初始位置的轮子是用实线绘制的，而最终位置是用虚线绘制的。

在任何时刻，如果车轮重心的y坐标减小，轮子就会围绕它的一个顶点(比如P)旋转(注意，在运动的任何时刻，这种情况都是必要的)。可以很容易地证明，在任何时刻，最多存在一个这样的顶点。当轮子接触到一个片段时，围绕P的旋转停止。这个运动继续下去，直到没有一个顶点可以让轮子绕着它旋转为止。在任何时刻，假设在任何方向上改变重心位置最多10-5个单位，都不会影响车轮的稳定性。同时假设轮子和山丘表面之间的摩擦力非常大，以至于轮子从不在表面上滑动。

输入

输入的第一行包含一个单一的整数t (1 <= t <= 10)，测试用例的数量，然后是每个测试用例的输入数据。在每个测试用例的第一行都有一个整数n (1 <= n <= 10)，它表示车轮顶点的数量。在接下来的每n行中，都有一对数字，它们是顶点初始位置的x和y坐标。在这之后，有一条单独的线包含车轮重心的初始x和y坐标。您可以假设重心在多边形的内部或边界上(注意，给定的重心不一定可以从车轮的几何形状计算出来)。测试数据的下一行将描述山的形状。山的表面近似为一系列斜坡逐渐减小的线段，以水平线结束。对于每个线段，都有一条包含线段长度和斜率的直线(它们都是实数)。这些线是按照斜率递减的顺序排列的(这部分输入的最后一行斜率为0)。你可以假设最后一条线(水平线)足够长，轮子不会通过它的末端。在测试用例的最后一行中，有一行包含第一个线段右端点的x和y坐标。所有坐标和斜率都是实数。

输出

对于每个测试用例，输出中应该有一行，包含两个数字，分别是车轮重心的x和y坐标。将输出的数字四舍五入到小数点后的3位。

Sample Input

1
4
40 30
30 37
24 30
30 26
27 29
30 1
100 0
40 30

Sample Output

28.854 20.031

题意

给你一个斜坡（从左往右，斜率越来越大），再给你一个多边形，再给你一个重心，然后问你最后这个多边形的重心会在哪里，假设地面摩擦力无穷大，且运动过程中重心必须时刻保持向下。

题解

我们先考虑一下简单的情况就是多边形往左边滚(即逆时针旋转)

设支撑点为q，重心为g，旋转角度为k

那么我们得满足什么条件呢

cos(angle(g-q))<=0

如何确定选择的角度呢？二分就行了，判断条件就是

1.我们把这个多边形围绕q点选择后，所有的点都在斜面的上面

2.cos(angle(g-q)+k)<=0

这样好像就行了

但是要注意一些坑点的就是可能会往右边滚，所以分一些情况就行了

代码：

#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
typedef struct
{
	double x,y;
}POINT;
int n;
const double pi=3.1415926;
//当前点的位置
POINT p[10],g;
//存储长度和斜率
vector<double> vl,vs;
//存储每条直线的起点和斜率.
vector<POINT> vp;
inline double dis(POINT p1,POINT p2)
{
    return sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) );
}

inline double dot(POINT p1,POINT p2,POINT p3)
{
    return (p3.x-p2.x)*(p1.x-p2.x)+(p3.y-p2.y)*(p1.y-p2.y);
}

double theta(POINT p2,POINT p1)
{
    double dx=p2.x-p1.x,dy=p2.y-p1.y,ret;
    if(dx==0)
    {
	if(dy>0)
	    return pi/2;
	else
	    return 1.5*pi;
    }
    else
    {
	ret=atan(dy/dx);
	if(dx>0)
	{
	    if(dy>=0)
		return ret;
	    else
	        return 2*pi+ret;
	}
	else
	    return pi+ret;	
    }
}
int main()
{
    int T;
    //cur_v,cur_l:当前旋转点所在的顶点和线段
    int i,j,cur_v,cur_l,flag;
    //dthe:旋转角度;tthe:角度变量
    double length,slope,dx,A,B,C,b,dthe,tthe,len;
    POINT tp;
    scanf("%d",&T);
    while(T--)
    {
	scanf("%d",&n);
	//input:输入多边形的顶点
	for(i=0;i<n;i++)
	    scanf("%lf%lf",&p[i].x,&p[i].y);
	scanf("%lf%lf",&g.x,&g.y);
	vl.clear();
	vs.clear();
        while(1)
	{
	    scanf("%lf%lf",&length,&slope);
	    vl.push_back(length);
	    vs.push_back(slope);
	    if(slope==0)
		break;
	}
        //第一条线段的右端点
	scanf("%lf%lf",&tp.x,&tp.y);
	vp.clear();
	vp.push_back(tp);
	for(i=1;i<vs.size();i++)
	{
	    dx=vl[i-1]/sqrt(1+vs[i-1]*vs[i-1]);
	    tp.x=vp[i-1].x-dx;
	    tp.y=vp[i-1].y-dx*vs[i-1];
	    vp.push_back(tp);
	}
	for(i=0;i<vl.size();i++)
	{
	    for(j=0;j<n;j++)
	        if( fabs( vs[i] * ( p[j].x - vp[i].x ) + vp[i].y - p[j].y ) <= 1e-6 )
		{
		    cur_l=i;
		    cur_v=j;
		    break;
		}
	    if(j<n)
		break;
	}
    	//上面得到的信息是旋转点在第i坡上,是多边形的第j个顶点
	if(vl.size()==1)
	{
	    if( g.x > p[cur_v].x )
		flag = 1;
	    else if(g.x < p[cur_v].x)
		flag = -1;
	    else
		break;
	    while(1)
	    {
		//找出以p[cur_v]为原点的偏移角度最大的点
		tthe=100;
		for(i=0;i<n;i++)
	            if( i!=cur_v && tthe - flag*theta(p[i],p[cur_v]) > 1e-9)
		    {
			tthe = flag*theta(p[i],p[cur_v]);
			j = i;
		    }
		len = dis(p[j],p[cur_v]);
		tp.x = p[cur_v].x + flag*len;
		tp.y = p[cur_v].y;
		dthe = theta(tp,p[cur_v]) - theta(p[j],p[cur_v]);
		for(i=0;i<n;i++)
		{
		    len=dis(p[cur_v],p[i]);
		    tthe=dthe+theta(p[i],p[cur_v]);
		    p[i].x=p[cur_v].x+len*cos(tthe);
		    p[i].y=p[cur_v].y+len*sin(tthe);
		}
		len=dis(g,p[cur_v]);
		tthe=dthe+theta(g,p[cur_v]);
		g.x=p[cur_v].x+len*cos(tthe);
		g.y=p[cur_v].y+len*sin(tthe);	
		cur_v = j;
		if(flag==1 && g.x <= p[cur_v].x)
		    break;
                if(flag==-1 && g.x >= p[cur_v].x)
		    break;
	    }
        }
	else
	{
	    while(1)
	    {	
		//找到下一个旋转点
		//找出以p[cur_v]为原点的偏移角度最大的点
		tthe=-100;
		for(i=0;i<n;i++)
		    if(i!=cur_v && tthe - theta(p[i],p[cur_v]) < 1e-9)
		    {
			tthe = theta(p[i],p[cur_v]);
			j = i;
		    }
		len=dis(p[j],p[cur_v]);
		for( ; cur_l+1<vl.size() && dis(p[cur_v],vp[cur_l+1])<len ; )
		    cur_l++;
		//A*x^2+B*x+C=0;
		b=vp[cur_l].y-vs[cur_l]*vp[cur_l].x;
		A=1+vs[cur_l]*vs[cur_l];
		B=vs[cur_l]*(b-p[cur_v].y)-p[cur_v].x;
		B*=2;
		C=p[cur_v].x*p[cur_v].x;
		C+=(b-p[cur_v].y)*(b-p[cur_v].y)-len*len;
		//取值小的那个,并把(-B-sqrt(B^2-4*A*C))/2/A=>2*C/(-B+sqrt(B^2-4*A*C))
		tp.x=2*C/(-B+sqrt(B*B-4*A*C));
		tp.y=vs[cur_l]*tp.x+b;	
		//将每个点都按一定角度旋转
		dthe = theta(tp,p[cur_v]) - theta(p[j],p[cur_v]);
		for(i=0;i<n;i++)
		{
		    len=dis(p[cur_v],p[i]);
		    tthe=dthe+theta(p[i],p[cur_v]);
		    p[i].x=p[cur_v].x+len*cos(tthe);
		    p[i].y=p[cur_v].y+len*sin(tthe);
		}
		len=dis(g,p[cur_v]);
		tthe=dthe+theta(g,p[cur_v]);
		g.x=p[cur_v].x+len*cos(tthe);
		g.y=p[cur_v].y+len*sin(tthe);
		//判断是否还会旋转
                if( g.x >= p[j].x )
		    break;
	        cur_v = j;
	    }
	}
	printf("%.3lf %.3lf\n",g.x,g.y);
    }
    return 0;


--- EOF ---