閱讀977 返回首頁    go 阿裏雲 go 技術社區[雲棲]

UVA之1398 - Meteor

【題目】

The famous Korean internet company nhn has provided an internet-based photo service which allows The famous Korean internet company users to directly take a photo of an astronomical phenomenon in space by controlling a high-performance telescope owned by nhn. A few days later, a meteoric shower, known as the biggest one in this century, is expected. nhn has announced a photo competition which awards the user who takes a photo containing as many meteors as possible by using the photo service. For this competition, nhn provides the information on the trajectories of the meteors at their web page in advance. The best way to win is to compute the moment (the time) at which the telescope can catch the maximum number of meteors.

You have n meteors, each moving in uniform linear motion; the meteor mi moves along the trajectory pi +t×vi over time t , where t is a non-negative real value, pi is the starting point of mi and vi is the velocity of mi . The point pi = (xi, yi) is represented by X -coordinate xi and Y -coordinate yi in the (X,Y) -plane, and the velocity vi = (ai, bi) is a non-zero vector with two components ai and bi in the (X, Y) -plane. For example, if pi = (1, 3) and vi = (-2, 5) , then the meteor mi will be at the position (0, 5.5) at time t = 0.5 because pi + t×vi = (1, 3) + 0.5×(-2, 5) = (0, 5.5) . The telescope has a rectangular frame with the lower-left corner (0, 0) and the upper-right corner (w, h) . Refer to Figure 1. A meteor is said to be in the telescope frame if the meteor is in the interior of the frame (not on the boundary of the frame). For exam! ple, in Figure 1, p2, p3, p4 , and p5 cannot be taken by the telescope at any time because they do not pass the interior of the frame at all. You need to compute a time at which the number of meteors in the frame of the telescope is maximized, and then output the maximum number of meteors.

\epsfbox{p3905.eps}

Input 

Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers w and h (1$ \le$w, h$ \le$100, 000) , the width and height of the telescope frame, which are separated by single space. The second line contains an integer n , the number of input points (meteors), 1$ \le$n$ \le$100, 000. Each of the next n lines contain four integers xi, yi, ai , and bi ; (xi, yi) is the starting point pi and(ai, bi) is the nonzero velocity vector vi of the i -th meteor; xi and yi are integer values between -200,000 and 200,000, and ai and bi are integer values between -10 and 10. Note that at least one of ai and bi is not zero. These four values are separated by single spaces. We assume that all starting points pi are distinct.

Output 

Your program is to write to standard output. Print the maximum number of meteors which can be in the telescope frame at some moment.

Sample Input 

2 
4 2 
2 
-1 1 1 -1 
5 2 -1 -1 
13 6 
7 
3 -2 1 3 
6 9 -2 -1 
8 0 -1 -1 
7 6 10 0 
11 -2 2 1 
-2 4 6 -1 
3 2 -5 -1

Sample Output 

1 
2

【分析】

不難發現，流星的軌跡是沒有直接意義的，有意義的隻是每個流星在照相機視野內出現的時間段。換句話說，我們把本題抽象為這樣一個問題：給出n個開區間(Li, Ri)，你的任務是求出一個數t，使得包含它的區間數最多（為什麼是開區間呢？請讀者思考）。開區間(Li, Ri)是指所有滿足Li < x <Ri的實數x的集合。

把所有區間畫到平行於數軸的直線上（免得相互遮擋，看不清楚），然後想象有一條豎直線從左到右進行掃描，則問題可以轉化為：求掃描線在哪個位置時與最多的開區間相交，如圖所示。


不難發現，當掃描線移動到某個區間左端點的“右邊一點點”時最有希望和最多的開區間相交（想一想，為什麼）。為了快速得知在這些位置時掃描線與多少條線段相交，我們再一次使用前麵提到的技巧：維護信息，而不是重新計算。

我們把“掃描線碰到一個左端點”和“掃描線碰到一個右端點”看成是事件（event），則掃描線移動的過程就是從左到右處理各個事件的過程。每遇到一個“左端點事件”，計數器加1；每遇到一個“右端點事件”，計數器減1。這裏的計數器保存的正是我們要維護的信息：掃描線和多少個開區間相交，如圖所示。


這樣，我們可以寫出這樣一段偽代碼。

 

將所有事件按照從左到右排序

while(還有未處理的事件) {

  選擇最左邊的事件E

  if(E是“左端點事件”) { cnt++; if(cnt > ans) ans = cnt; } //更新計數器和答案

  else cnt--; //一定是“右端點事件”

}

這段偽代碼看上去挺有道理，但實際上暗藏危險：如果不同事件的端點相同，那麼哪個排在前麵呢？考慮這樣一種情況——輸入是兩個沒有公共元素的開區間，且左邊那個區間的右端點和右邊那個區間的左端點重合。在這種情況下，兩種排法的結果截然不同：如果先處理左端點事件，執行結果是2；如果先處理右端點事件，執行結果是1。這才是正確答案。

這樣，我們得到了一個完整的掃描算法：先按照從左到右的順序給事件排序，對於位置相同的事件，把右端點事件排在前麵，然後執行上述偽代碼的循環部分。如果你對這個衝突解決方法心存疑慮，不妨把它理解成把所有區間的右端點往左移動了一個極小（但大於0）的距離。


【代碼】

/*********************************
*   日期：2014-5-12
*   作者：SJF0115
*   題號: 1398 - Meteor
*   地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4144
*   來源：UVA
*   結果：Accepted
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

#define N 100010

//確定區間的左右端點
void IntervalRL(int x,int a,int w,double& L,double& R){
    if(a == 0){
        //0 < x < w
        if(x <= 0 || x >= w){
            //無解
            R = L - 1;
        }
    }
    // -x/a < t < (w-x)/a
    else if(a > 0){
        L = max(L,-(double)x/a);
        R = min(R,(double)(w - x)/a);
    }
    // (w-x)/a < t < -x/a
    else if(a < 0){
        L = max(L,(double)(w - x)/a);
        R = min(R,-(double)x/a);
    }
}
//區間
struct Inter{
    //坐標位置
    double x;
    //判斷是左端點還是右端點
    int type;
    //重載 <
    bool operator <(const Inter& inter)const{
        return x < inter.x || (x == inter.x && type > inter.type);
    }
}Inters[N*2];

int main(){
    int T,w,h,n,i,x,y,a,b;
    //freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        int num = 0;
        //相機坐標
        scanf("%d%d%d",&w,&h,&n);
        for(i = 0;i < n;i++){
            double L = 0,R = 1e9;
            //x,y初始位置 a,b速度
            scanf("%d%d%d%d",&x,&y,&a,&b);
            //a b 不能同時為0
            if(a == 0 && b == 0){
                break;
            }
            //確定區間的左右端點
            IntervalRL(x,a,w,L,R);
            IntervalRL(y,b,h,L,R);
            //形成一個區間
            if(L < R){
                Inters[num].x = L;
                Inters[num++].type = 0;
                Inters[num].x = R;
                Inters[num++].type = 1;
            }//if
        }//for
        //排序
        sort(Inters,Inters+num);
        int cur = 0;
        int maxNum = 0;
        for(i = 0;i < num;i++){
            if(Inters[i].type == 0){
                cur++;
                maxNum = max(maxNum,cur);
            }
            else{
                cur--;
            }
        }//for
        printf("%d\n",maxNum);
    }//while
    return 0;
}


最後更新：2017-04-03 12:56:36

  上一篇：go 線段樹-poj-2823
  下一篇：go NYOJ891-找點