2014
02-24

# Rotating a Frame

Suppose you have an ice hockey ball (Which has the shape of a cylinder as shown in the figure) and a photo frame (a rectangle). You place the ball in one corner of the photo frame and keep the balls position and orientation fixed. Now you start rotating the frame in clockwise direction. But as the sides of the frame and of the ball have high friction so while the frame is rotating its surface and the balls surface never slips. So the frame always has a constant angular velocity as well as a tangential velocity as shown in the figure below.

Write a program to find the position of the frame after certain time.

he input contains several test cases. Each set of input is contained in two lines. The first line of a set contains eight integers which denote the values x1, y1, x2, y2, x3, y3 and x4, y4 respectively. These values indicate that the four vertices of the frame in clockwise order are denoted by the Cartesian coordinates P1 (x1, y1) , P2 (x2, y2) , P3 (x3, y3) and P4 (x4, y4) . You can assume that 0<=| x1|,| y1|,| x2|,| y2|,| x3|,| y3|,| x4|,| y4|<=1000 . The second line contains three floating point numbers which denotes the values of R (0 < R < 1000) , T (0<=T < 100000) and (0<= < 360) respectively. Here R is the radius of the ice hockey ball, T denotes that we want to know the position of the frame after T seconds and is the angular velocity of the frame in degree/second. You can assume that ball is placed touching two the si! des that intersect at point (x1, y1) and it never moves from or rotates in that position. There will be no such input where the hockey ball cannot be placed within the frame. The last test case is followed by a single zero, which should not be processed.

he input contains several test cases. Each set of input is contained in two lines. The first line of a set contains eight integers which denote the values x1, y1, x2, y2, x3, y3 and x4, y4 respectively. These values indicate that the four vertices of the frame in clockwise order are denoted by the Cartesian coordinates P1 (x1, y1) , P2 (x2, y2) , P3 (x3, y3) and P4 (x4, y4) . You can assume that 0<=| x1|,| y1|,| x2|,| y2|,| x3|,| y3|,| x4|,| y4|<=1000 . The second line contains three floating point numbers which denotes the values of R (0 < R < 1000) , T (0<=T < 100000) and (0<= < 360) respectively. Here R is the radius of the ice hockey ball, T denotes that we want to know the position of the frame after T seconds and is the angular velocity of the frame in degree/second. You can assume that ball is placed touching two the si! des that intersect at point (x1, y1) and it never moves from or rotates in that position. There will be no such input where the hockey ball cannot be placed within the frame. The last test case is followed by a single zero, which should not be processed.

0 1 1 1 1 0 0 0
0.2 10 0
0 1 1 1 1 0 0 0
0.2 10 100
0

Case 1: 0.000 1.000 1.000 1.000 1.000 0.000 0.000 0.000
Case 2: -0.619 0.132 -0.445 1.117 0.539 0.943 0.366 -0.042

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

double r,w,t;
char buf[500];

const double eps = 1e-8;
const double pi = acos(-1.0);

struct Point
{
double x,y;
Point() {}
Point(double _x,double _y)
{
x = _x;
y = _y;
}
Point(Point _a,Point _b)
{
x = _b.x-_a.x;
y = _b.y-_a.y;
}
void transXY(double B)
{
double tx = x,ty = y;
x = tx*cos(B) - ty*sin(B);
y = tx*sin(B) + ty*cos(B);
}
double Length()
{
return sqrt(eps+x*x+y*y);
}
};

int cmp(double a,double b)
{
if (fabs(a-b) < eps) return 0;
if (a < b) return -1;
return 1;
}

double sqr(double a)
{
return a*a;
}

Point p[4],res[4];

int main()
{
int ft = 0;
while (true)
{
gets(buf);
if (strlen(buf) == 1) break;
sscanf(buf,"%lf%lf%lf%lf%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y,&p[3].x,&p[3].y);
scanf("%lf%lf%lf",&r,&t,&w);
gets(buf);
w = pi*w/180;
double theta = w*t;
theta = theta-2*pi*floor(theta/(2*pi));
double l = r*w*t;
double totl = 0;
Point tv;
for (int i = 0; i < 4; i++)
{
tv = Point(p[i],p[(i+1)%4]);
totl += tv.Length()-2*r;
}
res[0] = p[0];
for (int i = 1;i < 4;i++)
{
tv = Point(p[i-1],p[i]);
tv.transXY(-theta);
res[i] = Point(res[i-1].x+tv.x,res[i-1].y+tv.y);
}
l = l-totl*floor(l/totl);
double pre = 0.0,len;
Point prep,nowp,xp;

tv = Point(p[0],p[1]);
len = tv.Length();
xp = Point(p[0].x+tv.x*r/len,p[0].y+tv.y*r/len);
prep = Point(xp.x+tv.y*r/len,xp.y-tv.x*r/len);

for (int i = 0; i < 4; i++)
{
tv = Point(res[i],res[(i+1)%4]);
len = tv.Length();
if (cmp(pre+len-2*r,l) >= 0)
{
l -= pre;
l += r;
xp = Point(res[i].x+tv.x*l/len,res[i].y+tv.y*l/len);
nowp = Point(xp.x+tv.y*r/len,xp.y-tv.x*r/len);
tv = Point(nowp,prep);
for (int j = 0;j < 4;j++)
res[j] = Point(res[j].x+tv.x,res[j].y+tv.y);
break;
}
pre += len-2*r;
}
ft++;
printf("Case %d:",ft);
for (int i = 0;i < 4;i++)
printf(" %.3f %.3f",res[i].x,res[i].y);
printf("\n");
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

3. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept