首页 > ACM题库 > HDU-杭电 > HDU 4410-Boomerang-计算几何-[解题报告]HOJ
2015
07-16

HDU 4410-Boomerang-计算几何-[解题报告]HOJ

Boomerang

问题描述 :

Australia original inhabitants used to hunt by a weapon called "boomerang". When a boomerang is thrown out, it rotates, hits the target, and then return to the thrower. ZXX is the best boomerang thrower in Australia. His skill is so wonderful that his boomerang can do any rotation he wants in the air. He travels around to show his skill and make money. One of his classic show is to throw out the boomerang, and it will pass through between two very close pillars. Of course the boomerang must fly parallel to the ground. If not so, everybody can do it. ZXX always puts the two pillars as close as possible to show his skill, but he wants you to figure out the smallest distance between two pillars which allows his boomerang to go through.

To simplify the problem, you can consider the boomerang as a simple polygon in a 2D plane, and each of its edge is parallel to x-axis or y-axis. Each interior angle is either 90 degrees or 270 degrees. Two pillars can be considered as two points.

This illustration simply shows how a boomerang passes through two pillars:

Family Name List

输入:

The input consists of several test cases (less than 500).Each test case begins with an integer n (4<=n<=8), representing the number of vertices of a polygon. Next n lines give coordinates of n vertices in order. Each line contains two integers xi, yi(|xi|, |yi|<=100000). For each test case there are no two vertices is in the same place.

Input ends with n=0.

输出:

The input consists of several test cases (less than 500).Each test case begins with an integer n (4<=n<=8), representing the number of vertices of a polygon. Next n lines give coordinates of n vertices in order. Each line contains two integers xi, yi(|xi|, |yi|<=100000). For each test case there are no two vertices is in the same place.

Input ends with n=0.

样例输入:

6
0 0
100 0
100 1
1 1
1 100
0 100
8
0 0
30 0
30 30
20 30
20 10
10 10
10 30
0 30
0

样例输出:

1.41
14.14

题意:  

思路:每一条边不是平行就是竖直,且最多只有8个点,所以可以枚举每一种可能的形状,

4个点的只可能是矩形,

6个点的只可能是矩形缺一个角,

8个点的可以是6个点的其中三个90度角缺一个小脚,或者是凹形。。。。

不可能是奇数个点。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const double INF = 1e19;
double EPS = 1e-12;
bool zero(double t){return -EPS<t&&t<EPS;}
struct cvector{
    double x,y;
    cvector(double a,double b){x=a,y=b;}
    cvector(){}
};
cvector operator-(cvector a,cvector b){
    return cvector(a.x-b.x,a.y-b.y);
}
cvector operator+(cvector a,cvector b){
    return cvector(a.x+b.x,a.y+b.y);
}
double operator^(cvector a,cvector b){
    return a.x*b.y-b.x*a.y;
}
double operator*(cvector a,cvector b){
    return a.x*b.x+a.y*b.y;
}
struct cpoint{
    double x,y;
    void get(){scanf("%lf%lf",&x,&y);}
} p[19];
cvector operator-(cpoint a,cpoint b){
    return cvector(a.x-b.x,a.y-b.y);
}
double dist(cpoint a,cpoint b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct segline{
    cpoint a,b;
    segline(cpoint x,cpoint y){a=x,b=y;}
    segline(){}
};
bool intersect(segline s1,segline s2){
    return ((s1.a-s2.a)^(s2.b-s2.a))*((s1.b-s2.a)^(s2.b-s2.a))<-EPS&&
        ((s2.a-s1.a)^(s1.b-s1.a))*((s2.b-s1.a)^(s1.b-s1.a))<-EPS;
}
int n;
double solve4(){    ///四个点
    return min(fabs(p[0].x-p[2].x),fabs(p[0].y-p[2].y));
}
double solve6()     ///6个点
{
    double re[10];
    int t=0,k;
    for(int i=0;i<n;i++){
        re[i]=(p[i]-p[(i+n-1)%n])^(p[(i+1)%n]-p[i]);
        if(re[i]>0) t++;
    }
    if(t==1){
        for(int i=0;i<6;i++)
        if(re[i]>0) k=i;
    }else{
        for(int i=0;i<6;i++)
        if(re[i]<0) k=i;
    }
    return min(dist(p[k],p[(k+3)%n]),min(fabs(p[(k+2)%n].x-p[(k+n-2)%n].x),fabs(p[(k+2)%n].y-p[(k+n-2)%n].y)));
}
double oor6(int a,int  b)   ///8个点有6个连续的凸   即凹形
{
    cpoint t1 = p[(a+n-2)%n],t2 = p[(b+3)%n];
    return min(fabs(t1.x-t2.x),min(fabs(t1.y-t2.y),max(dist(p[a],p[(a+n-3)%n]),dist(p[b],p[(b+3)%n]))));
}
double oor5(int a,int b)    ///5个连续的凸   即楼梯形
{
    cpoint t1 = p[(a+n-2)%n],t2 = p[(b+2)%n];
    return min(fabs(t1.x-t2.x),min(fabs(t1.y-t2.y),min(dist(p[a],p[(a+n-3)%n]),dist(p[b],p[(b+3)%n]))));
}
double oor4(int a,int b)   ///四个连续的凸   T字形
{
    double ans;
    if(zero(p[(a-2+n)%n].y-p[(b+2)%n].y))
    {
        ans = min(fabs(p[(a-1+n)%n].x-p[(b+1)%n].x),fabs(p[(a-2+n)%n].y-p[(a+2)%n].y));
    }else{
        ans = min(fabs(p[(a-1+n)%n].y-p[(b+1)%n].y),fabs(p[(a-2+n)%n].x-p[(a+2)%n].x));
    }
    ans = min(ans,min(dist(p[a],p[(a-3+n)%n]),dist(p[b],p[(b+3)%n])));
    return ans;
}
double oor3(int a,int b)   /// 3个连续的凸  即一个矩形缺两个对角   。。。这个请款最多  最恶心了。
{
    cpoint t1 = p[(a+2)%n],t2 = p[(b+2)%n];
    double ans = min(fabs(t1.x-t2.x),fabs(t1.y-t2.y));
    double A1=INF,A2=INF,B1=INF,B2=INF;
    if(intersect(segline(p[a],p[(a+3)%n]),segline(p[(a+4)%n],p[(a+5)%n])))
    A1=min(dist(p[(a+1)%n],p[(a+2)%n]),dist(p[b],p[(a+1)%n]));
    if(intersect(segline(p[a],p[(a-3+n)%n]),segline(p[(a-4+n)%n],p[(a-5+n)%n])))
    A2=min(dist(p[(a-1+n)%n],p[(a-2+n)%n]),dist(p[b],p[(a-1+n)%n]));
    if(intersect(segline(p[b],p[(b+3)%n]),segline(p[(b+4)%n],p[(b+5)%n])))
    B1=min(dist(p[(b+1)%n],p[(b+2)%n]),dist(p[a],p[(b+1)%n]));
    if(intersect(segline(p[b],p[(b-3+n)%n]),segline(p[(b-4+n)%n],p[(b-5+n)%n])))
    B2=min(dist(p[(b-1+n)%n],p[(b-2+n)%n]),dist(p[a],p[(b-1+n)%n]));
    if(A1!=INF)
    ans = min(ans,max(B1,A1));
    if(A2!=INF)
    ans = min(ans,max(B2,A2));
   // if(B1!=INF)
   // ans = min(ans,max(dist(p[b],p[(b+5)%n]),B1));
   // if(B2!=INF)
   // ans = min(ans,max(dist(p[b],p[(b+3)%n]),B2));
    //double A = max(min(dist(p[a],p[(a+3)%n]),A1),min(dist(p[a],p[(a+5)%n]),A2));
   // double B = max(min(dist(p[b],p[(b+3)%n]),B1),min(dist(p[b],p[(b+5)%n]),B2));
    ans = min(ans,max(min(dist(p[a],p[(a-3+n)%n]),dist(p[b],p[(b+3)%n])),
                      min(dist(p[a],p[(a+3)%n]),dist(p[b],p[(b-3+n)%n]))));
    return ans;
}
double solve8()    ///8个点
{
    double re[10];
    int t=0;
    for(int i=0;i<n;i++){
        re[i]=(p[i]-p[(i+n-1)%n])^(p[(i+1)%n]-p[i]);
        if(re[i]>0) t++;
    }
    if(t==2){
    }else{
        for(int i=0;i<n;i++) re[i] = 0-re[i];
    }
    ///re[i]>0 wei ao
    int a,b;  ///ao dian
    int s = 0,k=0;
    for(int i=0;i<(n<<1);i++)
    {
        if(re[i%n]>0){
            s=max(s,k);
            k=0;
            if(i<n)
            a=b,b=i;
        }else{
            k++;
        }
    }
    if(b-a>4) swap(a,b);
    if(s==6)
    return oor6(a,b);
    if(s==5)
    return oor5(a,b);
    if(s==4)
    return oor4(a,b);
    if(s==3)
    return oor3(a,b);
    return 0;
}
int main()
{
    freopen("in.txt","r",stdin);
    while(scanf("%d",&n)&&n)
    {
        for(int i=0;i<n;i++)
            p[i].get();
        if(n==4)
        printf("%.2lf\n",solve4());
        if(n==6)
        printf("%.2lf\n",solve6());
        if(n==8)
        printf("%.2lf\n",solve8());
    }
    return 0;
}

先给组数据(跟taozifish一起想出来的)

8
-3 9
0 9
0 0
9 0
9 -2
1 -2
1 -1
-3 -1
8
-3 9
0 9
0 0
9 0
9 -4
1 -4
1 -1
-3 -1
8
3 0
4 0
4 1
8 1
8 2
4 2
4 3
3 3
8
0 0
6 0
6 3
10 3
10 4
5 4
5 2
0 2
8
0 0
2 0
2 19
3 19
3 40
1 40
1 20
0 20
0

结果是

3.16
4.00
2.24
2.24
2.24

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

参考:http://blog.csdn.net/binwin20/article/details/8011356