Arab Collegiate Programming Contest 2012G. Archery(求雷達掃描的期望，區間離散化)

G. Archery time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Last summer you were watching all the matches in the 2012 Olympics in London. One of the interesting sports is archery (it's the game of propelling arrows with the use of a bow to hit a target), but in this problem we are dealing with a new type of archery.

In this new type of archery, the player has arrows that can penetrate any target and can go to infinity (the same arrow may hit more than one target), and there will be a lot of targets around the player everywhere, and the targets may intersect and/or overlap with each others.

From the top view you can model the targets as line segments and the player as a point at the origin (point (0,0) is the origin), also there will be no target which intersects with the player's position.

You are really interested to calculate the expected number of targets this player can penetrate using one arrow, if he will shoot his arrow in a random direction (there are infinite number of different directions, and each direction has the same probability to be used for the random shoot).

For example, the following figure explains the first sample test, where the player is at the origin, and there are two targets T1 with end points (1,5) and (3,3), and T2 with end points (3,5) and (6,2), you can notice that there is a region where the player can shoot an arrow and penetrate the two targets, and there are two regions where he can penetrate only one target, and the last region he will not penetrate any target.

Note that a target can be hit at any point between its 2 end points (inclusive).

Input

The input starts with a line containing one integer N (1  ≤  N  ≤  100) representing the number of targets in the game. Followed by N lines, the ith line contains 4 integers separated by a single space X1 Y1 X2 Y2 (-100  ≤  X1, Y1, X2, Y2  ≤  100) representing the ith target end points (X1,Y1) and (X2,Y2).

Output

Print on a single line, the expected number of targets the player can penetrate using one arrow. The absolute or relative error in the answer should not exceed 10 - 6.

Sample test(s) input

2
1 5 3 3
3 5 6 2
      

output

0.206364895
      

input

8
3 0 0 3
0 3 -3 0
-3 0 0 -3
0 -3 3 0
3 3 -3 3
-3 3 -3 -3
-3 -3 3 -3
3 -3 3 3
      

output

2.000000000      

位址：http://codeforces.com/gym/100155/problem/G

本場過了5題，就這題有點意義，其他4題都是水題

這題可以形象地這樣子描述：

有一個雷達在原點(0,0)，有n條線段在平面上，線段不會通過原點，雷達可以在任意角度進行掃描，雷達的電磁波可以射到無限遠，穿透所有線段

問，雷達在繞一圈内，能夠打到的線段個數的期望。

這題要用正确的區間離散化方法來處理，把每一個端點對應的角度适當離散化，适當建立線段和區間的結構體。

複雜度是O(n*logn)，注意數組的範圍，有時候可能要開到2*n或者4*n.

(題目有點水，其實n=10^5都可以處理)

代碼如下：

//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN
#define N 10010
#define M
int dcmp(double x){
    if(fabs(x)<eps) return 0;
    else if(x<0) return -1;
    else return 1;
}
struct Segment{
    double angle1,angle2;
}seg[2*N];
int n,num_seg;
double xx1,yy1,xx2,yy2,angle1,angle2,ans;
double GetAngle(double x,double y){
    double res=atan2(y,x);
    if(res<0) res+=2*pi;
    return res;
}
struct Interval{
    double angle1,angle2;
}interval[2*N];
int num_interval;
set<double>angleset;
set<double>::iterator setit;
map<double,int>leftbelong,rightbelong;
map<double,int>::iterator mapit;
int intervalnum[2*N];
int main()
{
    cin>>n;
    num_seg=0;
    repin(i,1,n){
        scanf("%lf %lf %lf %lf",&xx1,&yy1,&xx2,&yy2);
        angle1=GetAngle(xx1,yy1);
        angle2=GetAngle(xx2,yy2);
        if(!dcmp(angle1-angle2)) continue;
        if(dcmp(angle1-angle2)>0) swap(angle1,angle2);
        double d=angle2-angle1;
        if(dcmp(d-pi)<0){
            int t=++num_seg;
            seg[t].angle1=angle1;
            seg[t].angle2=angle2;
        }
        else{
            int t=++num_seg;
            seg[t].angle1=angle2;
            seg[t].angle2=2*pi;
            t=++num_seg;
            seg[t].angle1=0.0;
            seg[t].angle2=angle1;
        }
    }
    angleset.clear();
    repin(i,1,num_seg){
        angleset.insert(seg[i].angle1);
        angleset.insert(seg[i].angle2);
    }
    int num=0;
    double last=0.0;
    num_interval=0;
    leftbelong.clear(),rightbelong.clear();
    for(setit=angleset.begin();setit!=angleset.end();setit++){
        num+=1;
        if(num==1){
            last=*setit;
            continue;
        }
        int t=++num_interval;
        interval[t].angle1=last;
        interval[t].angle2=*setit;
        leftbelong[last]=t;
        rightbelong[*setit]=t;
        last=*setit;
    }
    repin(i,1,num_seg){
        int leftbe=leftbelong[seg[i].angle1];
        int rightbe=rightbelong[seg[i].angle2];
        repin(j,leftbe,rightbe){//這裡可以懶操作優化
            intervalnum[j]+=1;
        }
    }
    ans=0.0;
    double d;
    repin(i,1,num_interval){
        d=interval[i].angle2-interval[i].angle1;
        ans+=intervalnum[i]*(d/(2*pi));
    }
    printf("%.9f\n",ans);
}