首页 > ACM题库 > HDU-杭电 > HDU 4491-Windmill Animation-模拟-[解题报告]HOJ
2015
07-17

HDU 4491-Windmill Animation-模拟-[解题报告]HOJ

Windmill Animation

问题描述 :

A windmill animation works as follows:
A two-dimensional set of points, no three of which lie on a line is chosen. Then one of the points is chosen (as the first pivot) and a line is drawn through the chosen point at some initial angle. The animation proceeds by rotating the line counter-clockwise about the pivot at a constant rate. When the line hits another of the points, that point becomes the new pivot point. In the two examples below, the points are (-1,1), (1,1), (0,0), (-1,-2) and (1,-2).
Mad Veterinarian

Example 1

In Example 1, the start point is point 1 and the line starts rotated 45 degrees from horizontal. When the line rotates to 90 degrees, point 4 is hit and becomes the new pivot. Then point 5 becomes the new pivot, then point 2 then point 1.

Mad Veterinarian

Example 2

In Example 2, the initial point is point 3 and the line starts horizontal. At 45 degrees, point 2 becomes the pivot, then at about 56 degrees, point 4 becomes the pivot. At about 63 degrees, point 3 becomes the pivot again, then point 5, point 1 and back to 3 as at the start.

Write a program, which takes as input the points of the set, the initial point and the initial line angle and outputs the sequence of pivot points.

输入:

The first line of input contains a single integer P, (1<= P <= 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of multiple lines of input. The first line of each data set consists of four space- separated decimal integers followed by a single floating-point value. The first integer is the data set number. The second integer is the number of points M to follow (3 <= M <= 20). The third integer gives the number, s , of the pivot points to output (3 <= s <= 20) and the fourth integer gives the index, I, of the initial point (1 <= I <= M). The floating-point value is the angle, A, in degrees, that the initial line is rotated counter-clockwise from horizontal (0 <= A < 180).

The remaining M lines in the data set contain the coordinates of the set of points. Each line consists of an integer, the point.s index, I, and two floating-point values, the X and Y coordinates of the point respectively.

输出:

The first line of input contains a single integer P, (1<= P <= 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of multiple lines of input. The first line of each data set consists of four space- separated decimal integers followed by a single floating-point value. The first integer is the data set number. The second integer is the number of points M to follow (3 <= M <= 20). The third integer gives the number, s , of the pivot points to output (3 <= s <= 20) and the fourth integer gives the index, I, of the initial point (1 <= I <= M). The floating-point value is the angle, A, in degrees, that the initial line is rotated counter-clockwise from horizontal (0 <= A < 180).

The remaining M lines in the data set contain the coordinates of the set of points. Each line consists of an integer, the point.s index, I, and two floating-point values, the X and Y coordinates of the point respectively.

样例输入:

2
1  5  5  1  45
1  -1  1
2  1  1
3  0  0
4  -1  -2
5  1  -2
2  5  7  3  0
1  -1  1
2  1  1
3  0  0
4  -1  -2
5  1  -2

样例输出:

1 4 5 2 1 4
2 2 4 3 5 1 3 2

给定平面上的n(n<=20)个点,不存在三点共线。然后每次用某条直线(原点及斜率)逆时针旋转,每碰到一个点后,更换原点跟斜率。求出前s个原点。

考虑到n很小,可以模拟来搞。每次得到一个原点及斜率,然后构造出在直线上原点(O)的上方(rp)和下方(rn)两个点。然后依次每个不在该直线上的点,如果该点在直线上方,那么要达到该点逆时针旋转的角度为向量 rp->O 和向量 p->O的夹角。反之则是向量O->rp和向量O->rn的夹角。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<sstream>
#include<cstdlib>
#include<vector>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
#define MP make_pair
using namespace std;

const double eps = 1e-8;
const double PI = acos(-1.0);
int dcmp(double x) {
  if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}

struct Point {
  double x, y;
  Point(double x=0, double y=0):x(x),y(y) { }
};

typedef Point Vector;

Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }

bool operator < (const Point& a, const Point& b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool operator == (const Point& a, const Point &b) {
  return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}

double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A, A)); }
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }
double angle(Vector v) { return atan2(v.y, v.x); }
double torad(double ang)
{
    return ang / 180 * PI;
}

void getLineGeneralEquation(const Point& p1, const Point& p2, double& a, double& b, double &c) {
  a = p2.y-p1.y;
  b = p1.x-p2.x;
  c = -a*p1.x - b*p1.y;
}

Point read_point()
{
    Point a;
    scanf("%lf%lf", &a.x, &a.y);
    return a;
}

const int maxn = 30;
int P, cas, ind, n, s, st, ans[maxn];
double ang;
Point p[maxn];

int main()
{
    scanf("%d", &P);
    while(P--)
    {
        scanf("%d%d%d%d%lf", &cas, &n, &s, &st, &ang);
        ang = torad(ang);
        FF(i, 1, n+1)
        {
            scanf("%d", &ind);
            p[ind] = read_point();
        }
        int tot = 0, id1 = st, id2 = st;
        Point now = p[st];
        while(tot < s)
        {
            int nxt;
            double a, b, c, tmp, tang, nxtang = 1e50;
            Point O = now, rp = O + Point(1000*cos(ang), 1000*sin(ang)) , rn = O - Point(1000*cos(ang), 1000*sin(ang));
            getLineGeneralEquation(O, rp, a, b, c);
            FF(i, 1, n+1) if(i != id1 && i != id2)
            {
                tmp = a*p[i].x + b*p[i].y + c;
                if(tmp > 0) tang = Angle(rn-O, p[i]-O);
                else if(tmp < 0) tang = Angle(rp-O, p[i]-O);
                else tang = 0;
                if(dcmp(nxtang - tang) > 0) nxtang = tang, nxt = i;
            }
            ans[tot++] = nxt;
            ang = angle(now-p[nxt]);
            now = p[nxt];
            id1 = id2;
            id2 = nxt;
        }
        printf("%d", cas);
        REP(i, tot) printf(" %d", ans[i]);
        puts("");
    }
    return 0;
}

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

参考:http://blog.csdn.net/diary_yang/article/details/12855727