首页 > ACM题库 > HDU-杭电 > HDU 3365-New Ground-计算几何-[解题报告]HOJ
2014
03-16

HDU 3365-New Ground-计算几何-[解题报告]HOJ

New Ground

问题描述 :

Your school has a large ground. Recently the school wants a new ground similar to the former one.
The ground is a simple polygon. Suppose it has n edges and the old one is A0,A1,…,An-1, the new one is B0,B1,…,Bn-1.
They must be one-to-one mapping.
The new ground can be only worked out by rotating, expanding, contracting and shifting, but not flipping.
Now you know all the points of the old ground, B0, and B1. Can you calculate the other points of the new ground?

输入:

The first line contains one integer T representing the number of test cases.
For each case, first line contains one integer n (3<=n<=10000).
Then n lines follow. The i-th line has two integers representing the coordinate of the point Ai. (For each 0<=i<j<n, Ai doesn’t equals Aj)
Following one line contains four integers. The first two integers represent the coordinate of the point B0, and the second two integers represent the coordinate of the point B1. B0 never equals B1.
All coordinates are within [-10000, 10000].
The old ground always has a positive area.

输出:

The first line contains one integer T representing the number of test cases.
For each case, first line contains one integer n (3<=n<=10000).
Then n lines follow. The i-th line has two integers representing the coordinate of the point Ai. (For each 0<=i<j<n, Ai doesn’t equals Aj)
Following one line contains four integers. The first two integers represent the coordinate of the point B0, and the second two integers represent the coordinate of the point B1. B0 never equals B1.
All coordinates are within [-10000, 10000].
The old ground always has a positive area.

样例输入:

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

样例输出:

Case 1:
2.00 0.00
2.00 2.00
0.00 0.00
Case 2:
5.00 0.00
5.00 1.00
4.50 1.00
4.50 0.00

题意,给定点A[0~n-1]和B[0],B[1],

A[0]、A[1]映射到B[0]、B[1],求出其余点的映射B[2]~B[n-1],

思路,平移到远点,旋转、伸缩,再平移回去

#include<stdio.h>
#include<math.h>
#define N 10010
#define PI acos(-1)
#define EPS 1e-8
struct Point
{
    double x,y;
    void input(){scanf("%lf%lf",&x,&y);}
    void output(){printf("%.2lf %.2lf\n",x,y);}
}A[N],B[2],PA,PB;

double cosa,sina,k;
double length(Point P)
{
    return sqrt(P.x*P.x+P.y*P.y);
}
void rotate(Point &P)
{
    double t=P.x;
    P.x=P.x*cosa-P.y*sina;
    P.y=P.y*cosa+t*sina;
}
void expand(Point &P)
{
    P.x*=k;
    P.y*=k;
}

int main()
{
    int n,i,t,cnt=0;
    double a;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;++i)
            A[i].input();
        for(i=0;i<2;++i)
            B[i].input();
        PA.x=A[1].x-A[0].x;
        PA.y=A[1].y-A[0].y;
        PB.x=B[1].x-B[0].x;
        PB.y=B[1].y-B[0].y;
        a=acos((PA.x*PB.x+PA.y*PB.y)/(length(PA)*length(PB)));
        if(PA.x*PB.y-PA.y*PB.x<EPS)
            a = 2.0 * PI - a;
        cosa=cos(a);
        sina=sin(a);
        ///这里傻了好久,sin可能为负,不能开根号去求的
        //sina=sqrt(1.0-cosa*cosa);
        k=length(PB)/length(PA);

        for(i=2;i<n;++i)
        {
            A[i].x-=A[0].x;
            A[i].y-=A[0].y;
            rotate(A[i]);
            expand(A[i]);
            A[i].x+=B[0].x;
            A[i].y+=B[0].y;
        }
        printf("Case %d:\n",++cnt);
        B[0].output();
        B[1].output();
        for(i=2;i<n;++i)
            A[i].output();
    }
    return 0;
}

用c++中的复数类写真的是又简洁有强大

#include<stdio.h>
#include<complex>
using namespace std;

const int N=10010;
int main()
{
    int n;
    int i,cnt=0,t;
    complex<double> A[N],B[2],r,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;++i)
            scanf("%lf%lf",&A[i].real(),&A[i].imag());
        scanf("%lf%lf",&B[0].real(),&B[0].imag());
        scanf("%lf%lf",&B[1].real(),&B[1].imag());
        a=A[0];
        r=(B[1]-B[0])/(A[1]-A[0]);
        printf("Case %d:\n",++cnt);
        for(i=0;i<n;++i)
        {
            b=(A[i]-a)*r+B[0];
            printf("%.2lf %.2lf\n",b.real(),b.imag());
        }
    }
    return 0;
}

New Ground

参考:http://blog.csdn.net/cscj2010/article/details/7473045


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。