首页 > ACM题库 > HDU-杭电 > HDU 4197-Popping Balloons-计算几何-[解题报告]HOJ
2015
05-23

HDU 4197-Popping Balloons-计算几何-[解题报告]HOJ

Popping Balloons

问题描述 :

John loves programming contests. There is just one problem: his team is not very good at programming. This usually doesn’t bother him, but what does bother him is that everyone gets a balloon for every correct submission. John’s team never gets any balloons, while other teams get one balloon after the other. This frustrates him, so John would like to see that all other teams have no balloons either.
This year he has a plan to achieve just that. John has hired a ninja to pop all balloons for him. At any time during the contest, he can call for the ninja to come down through a hole in the ceiling and pop all balloons by using his shurikens (ninja stars), before leaving through the hole in the ceiling again. Of course the ninja wants to use as few of his precious shurikens as possible. Therefore, John must write a program that computes how many shurikens are needed to pop all balloons. Because all balloons are usually at approximately the same height, he can model the problem as a 2-dimensional problem. He sets the location of the ninja (where he comes in) as the origin (0, 0) and uses circles to model the balloons. To be on the safe side, these circles can have different radii. Shurikens are assumed to be thrown from the origin and move in a straight line. Any circle/balloon crossed by this haline will be popped by this shuriken. The question then becomes: how many halines rooted at the origin are necessary to cross all circles?
Of course, as mentioned above, John is not a very good programmer, so he asks you to make this program for him. Can you help him out? You might get a balloon if you get it right…
Remoteland

输入:

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with a single integer n (0 <= n <= 1,000): the number of balloons.
2.n lines, each containing three integers xi,yi (-10^4 <= xi,yi <= 10^4), and ri (1 <= ri <= 10^4),describing the circle used to model the ith balloon, where (xi, yi) is the center of the circle and ri is the radius.
You can assume that two lines (rooted at the origin) that are tangent to two distinct circles make an angle of at least 10^-6 radians at the origin. Furthermore, the circles do not cross each other (but can touch) and do not contain the origin.

输出:

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with a single integer n (0 <= n <= 1,000): the number of balloons.
2.n lines, each containing three integers xi,yi (-10^4 <= xi,yi <= 10^4), and ri (1 <= ri <= 10^4),describing the circle used to model the ith balloon, where (xi, yi) is the center of the circle and ri is the radius.
You can assume that two lines (rooted at the origin) that are tangent to two distinct circles make an angle of at least 10^-6 radians at the origin. Furthermore, the circles do not cross each other (but can touch) and do not contain the origin.

样例输入:

2 
5 
2 0 1
5 0 2
0 3 2
-4 0 2
0 -2 1
5
4 1 3
5 -5 3
0 -4 2
-4 4 3
-10 3 3

样例输出:

4
3
Hint
No balloons were harmed during the making of this problem.

题意:输入n个圆,所有圆不覆盖原点,从原点至少发出多少条射线能穿过所有圆。(0<=n<=1000)

解法:讲每个圆转化为角度区间 [ s , e ] ,区间范围 [ 0 ,  2*Pi ) ,得到n段区间后按e值增序将区间排序,枚举起点进行贪心。

复杂度:O(n*n)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const double EP=1e-8;
const double Pi=acos(-1.0);
int n;
struct Point{
    double x, y, r, loc, s, e;
}p[1005];
bool cmp(Point p1, Point p2){
    return p1.e<p2.e;
}
bool inside(double t1, double st, double end){
    if(st<end) return t1>=st&&t1<=end;
    else return t1>=st||t1<=end;
}
int main(){
    //freopen("1.txt", "r", stdin);
    int T, i, j, k, ans, cnt;
    double t, d;
    scanf("%d", &T);
    while(T–){
        scanf("%d", &n);
        ans=n;
        for(i=0; i<n; i++){
            scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].r);
            d=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);
            t=asin(p[i].r/d);
            if(fabs(p[i].x)<EP){
                if(p[i].y>0)p[i].loc=Pi*0.5;
                else p[i].loc=Pi*1.5;
            }
            else {
                p[i].loc=atan(fabs(p[i].y/p[i].x));
                if(p[i].x<0&&p[i].y>=0)p[i].loc=Pi-p[i].loc;
                else if(p[i].x>0&&p[i].y<0)p[i].loc=2*Pi-p[i].loc;
                else if(p[i].x<0&&p[i].y<0)p[i].loc+=Pi;
            }
            p[i].s=p[i].loc-t;
            if(p[i].s<-EP)p[i].s+=2*Pi;
            p[i].e=p[i].loc+t;
            if(p[i].e>=2*Pi-EP)p[i].e-=2*Pi;
        }
        sort(p, p+n, cmp);
        for(i=0; i<n; i++){
            cnt=1;
            double t2=p[i].e;
            for(j=1; j<n; j++){
                if(!inside(t2, p[(i+j)%n].s, p[(i+j)%n].e)){
                    t2=p[(i+j)%n].e;
                    cnt++;
                }
            }
            if(cnt<ans)
            ans=cnt;
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

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

参考:http://blog.csdn.net/taozifish/article/details/7542073