首页 > ACM题库 > HDU-杭电 > HDU 3116-Bus Schedules-计算几何-[解题报告]HOJ
2014
03-02

HDU 3116-Bus Schedules-计算几何-[解题报告]HOJ

Bus Schedules

问题描述 :

The Association of Commuters in Montreal (ACM) wishes to create a website for the city’s publictransit commuters, in order to promote public transit. A prominent reason for people to drive to work instead of commuting is the time wasted on the subway and buses. For this reason, the ACM wishes to add a form on their website so that visitors will be able to specify two points on the island, and the website will find the quickest route between those two points using its database of subway and bus schedules.
Cover the Square

Seeing how this may help improve the environment and the greenhouse effect, you offer your help.

输入:

The first line of each test case will contain a positive integer n, the number of bus and subway schedules which will follow. Each schedule will begin with a line containing a positive integer m, the number of stops along the path. m lines will follow, describing the stops of the day in chronological order. Each stop will begin by a time in the format hh : mm, between 00 : 00 and 23 : 59 inclusively. There will be at least one minute between each stop ― in other words, all the stop times for a particular bus will be different. A single space will follow, and the rest of the line will contain a name describing the stop.

The name will not contain spaces nor capital letters, and will be at most 20 characters long. Stops with the same name obviously denote the same physical location, where passengers can wait for other buses or subways to stop. After the day completes, the buses and subways mysteriously disappear and reappear at some point before their first stop. They cannot carry any passengers at that time, so the passengers must spend the night waiting at some stop.Each schedule repeats itself every day.

After the schedules, a line will contain a time and two locations of at most 20 characters, the start and the goal. Output the minimum number of minutes needed for a passenger at the start location at the given time to reach the goal location. He is able to enter any bus which stops at his start location at the given starting time or later, and he can also switch from a bus to another instantaneously if they happen to stop at the same place at the same time. He can also wait at a stop for an arbitrary amount of time.

输出:

The first line of each test case will contain a positive integer n, the number of bus and subway schedules which will follow. Each schedule will begin with a line containing a positive integer m, the number of stops along the path. m lines will follow, describing the stops of the day in chronological order. Each stop will begin by a time in the format hh : mm, between 00 : 00 and 23 : 59 inclusively. There will be at least one minute between each stop ― in other words, all the stop times for a particular bus will be different. A single space will follow, and the rest of the line will contain a name describing the stop.

The name will not contain spaces nor capital letters, and will be at most 20 characters long. Stops with the same name obviously denote the same physical location, where passengers can wait for other buses or subways to stop. After the day completes, the buses and subways mysteriously disappear and reappear at some point before their first stop. They cannot carry any passengers at that time, so the passengers must spend the night waiting at some stop.Each schedule repeats itself every day.

After the schedules, a line will contain a time and two locations of at most 20 characters, the start and the goal. Output the minimum number of minutes needed for a passenger at the start location at the given time to reach the goal location. He is able to enter any bus which stops at his start location at the given starting time or later, and he can also switch from a bus to another instantaneously if they happen to stop at the same place at the same time. He can also wait at a stop for an arbitrary amount of time.

样例输入:

2
4
00:01 loc_a
00:02 loc_b
00:10 loc_c
00:20 loc_a
2
00:02 loc_b
00:04 loc_c
00:00 loc_a loc_c
1
3
00:00 foo
01:00 bar
02:00 baz
01:30 bar foo
1
4
00:00 baz
01:00 foo
02:00 bar
03:00 baz
02:30 bar foo
0

样例输出:

4
impossible
2790

Background

At the last minute of the fighting between heroes and Deathwing, who wants to destroy the whole Azeroth, these last guardians of Azeroth are facing a severe test. Deathwing has a powerful AOE (Area of Effect) ability that will kill all lives in a circle of radius R immediately.

Bus Schedules 

In order to help heroes defeat Deathwing, guardian dragons have exhausted all of their mana to restrict Deathwing using his power so that Deathwing can only fire in narrow range. To prevent heroes from danger, Thrall wants to know the area of the region which could be fired by Deathwing. Thrall has labeled the region of the center of Deathwing’s AOE circle, and the important task of saving the world is counting on you. The description of the region consist of several arcs, and these arcs connected end to end to form the boundary of the region. In order to simplify the problem, no tangent of these arcs will intersect with any arc, and the central angle of each arc will less than PI.

Input 

There are several tests. For each test case, there are 2 numbers in the first line N and R, indicate the amount of arcs and the radius of AOE. It is followed by N lines, containing 3 numbers(xi, yi and ri) each in counterclockwise order. For i-th arc, (xi, yi) is the coordinate of the starting point , and ri is the radius of curvature. It is obvious that the i-th starting point is the (i-1)-th ending point, and the first starting point is the N-th ending point.

You may assume 1<N<1000, 0<R, ri<1000, -1000<xi, yi<1000.

Output 

For each test cases, you need print a number accurate to 0.01 in one line.

Sample Input

2 2
0 1 2
0 -1 2

Sample Output

21.67

HintBus Schedules

 

 

 

本题是上学期周赛一题。当时我认为这种题目我是一辈子也做不出来了。如今再看这题……哎

我因为叉积又忘了除以2,所以WA了好多次,大家不要和我一样- -

 

是这样,我们要求的是这个:

Bus Schedules

 

现在拆成这个:

其中涂黑部分删去:

Bus Schedules

 

1.

左边的那个,可以这么求:

对任意一个扇形-三角形:

 

扇形=0.5*PI*角度*(r+aoe)*(r+aoe)(aoe是题目中给出的R,就是AOE,小鸟的攻击范围)

每个三角形,这里最好的计算方式不是叉积而是海伦公式,毕竟三边都有,而坐标未知

 

2.

对于左下角那个,太好求了,就是叉积。

 

3.左上角那个也不难,就要看看这些小扇形的角度之和totangle

面积将是:

0.5*totangle*aoe*aoe*PI

 

totangle显然就是多边形内角和减去所有画左边等腰三角形们的腰角和

 

具体看代码。

哦对了,这个代码我显示两个,一个是速度慢的,一个是快的。慢一点的那个是用结构体写的。慢而易懂

 

慢而长:

/********* 
    *HOJ    3116 
    *codelength 1234 B 
    *mem    740K( the truth is : 14*sizeof(double) + sizeof(int) ) 
    *time   0.02S(slower) 
*********/
#include <cstdio> 
#include <cmath> 
const double PI=acos(-1); 
struct point{ 
    double x,y; 
    point(){} 
    point(double xx,double yy):x(xx),y(yy){} 
    friend point operator - (point a,point b){ 
        return point(a.x-b.x,a.y-b.y); 
    } 
}fst,ori,nex; 
double _cross(point a,point b){ 
    return a.x*b.y-a.y*b.x; 
} 
double dis(point a,point b){ 
    return sqrt((a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x)); 
} 
int n; 
double aoe,stot,l,ang,rnow,rnex,ans; 
double helen(double a,double b,double c){ 
    double p=(a+b+c)/2; 
    return sqrt((p-a)*(p-b)*(p-c)*p); 
} 
int main(){ 
    while(scanf("%d%lf",&n,&aoe)==2){ 
        ang=ans=stot=0; 
        scanf("%lf%lf%lf",&fst.x,&fst.y,&rnow); 
        ori=fst; 
        for(int i=1;i<n;i++){ 
            scanf("%lf%lf%lf",&nex.x,&nex.y,&rnex); 
            stot+=_cross(nex-fst,ori-fst)*0.5; 
            l=dis(nex,ori); 
            ang+=acos(l/(2.0*rnow)); 
            ans+=(asin(l/(2.0*rnow))*(rnow+aoe)*(rnow+aoe)-helen(rnow,rnow,l)); 
            rnow=rnex; 
            ori=nex; 
        } 
        l=dis(fst,ori); 
        ang+=acos(l/(2.0*rnow)); 
        ans+=(asin(l/(2.0*rnow))*(rnow+aoe)*(rnow+aoe)-helen(rnow,rnow,l)); 
        ans+=(ang-((double)n-2.0)*PI/2.0)*aoe*aoe + fabs(stot); 
        printf("%.2lf\n",ans); 
    } 
    return 0; 
}

快而短:

 

/********* 
    *HOJ    3116 
    *codelength:1195 B 
    *mem    740K( the truth is : 14*sizeof(double) + sizeof(int) ) 
    *time   0.02S(faster) 
*********/
#include <cstdio> 
#include <cmath> 
const double PI=acos(-1); 
double _cross(double ax,double ay,double bx,double by){ 
    return ax*by-ay*bx; 
} 
double dis(double ax,double ay,double bx,double by){ 
    return sqrt((ay-by)*(ay-by)+(ax-bx)*(ax-bx)); 
} 
int n; 
double aoe,stot,l,ang,rnow,rnex,ans,fstx,fsty,orix,oriy,nexx,nexy; 
double helen(double a,double b,double c){ 
    double p=(a+b+c)/2; 
    return sqrt((p-a)*(p-b)*(p-c)*p); 
} 
int main(){ 
    while(scanf("%d%lf",&n,&aoe)==2){ 
        ang=ans=stot=0; 
        scanf("%lf%lf%lf",&fstx,&fsty,&rnow); 
        orix=fstx; 
        oriy=fsty; 
        for(int i=1;i<n;i++){ 
            scanf("%lf%lf%lf",&nexx,&nexy,&rnex); 
            stot+=_cross(nexx-fstx,nexy-fsty,orix-fstx,oriy-fsty)*0.5; 
            l=dis(nexx,nexy,orix,oriy); 
            ang+=acos(l/(2.0*rnow)); 
            ans+=(asin(l/(2.0*rnow))*(rnow+aoe)*(rnow+aoe)-helen(rnow,rnow,l)); 
            rnow=rnex; 
            orix=nexx; 
            oriy=nexy; 
        } 
        l=dis(fstx,fsty,orix,oriy); 
        ang+=acos(l/(2.0*rnow)); 
        ans+=(asin(l/(2.0*rnow))*(rnow+aoe)*(rnow+aoe)-helen(rnow,rnow,l)); 
        ans+=(ang-((double)n-2.0)*PI/2.0)*aoe*aoe + fabs(stot); 
        printf("%.2lf\n",ans); 
    } 
    return 0; 
}

参考:http://hi.baidu.com/mytalent/item/9255e4fb4adca944922af27f


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