UVALive 6324 Archery

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4335

题目大意：

在二维坐标系中有n条不过原点的线段，可从源点任意角度发出一条射线，求该射线能穿过的线段数的期望值。

题目思路：

求出所有线段端点与源点连线的角度（0度 在x轴正方向），如果有一条线段两端点的角度差超过180度，则给角度小的加360度，原因画个图就知道了。

这样对所有的角度进行排序之后，这样就很好求在某段角度范围内能穿过几条线段了。

代码：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

//#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-8)
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define _mod(x,y) ((x)>0? (x)%(y):((x)%(y)+(y))%(y))
#define _abs(x) ((x)<0? (-(x)):(x))
#define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x))
#define getmax(x,y) (x= ((y)>(x))? (y):(x))
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
int TS,cas=1;
const double PI=acos(-1.0);
const int M=100+5;
struct node{
	double t1,t2;
}p[M];
double a[M<<2],cnt[M];
int X1,Y1,X2,Y2;
int n,m;

double getA(int x,int y){
	if(x==0) return (y>0)? 0.5*PI:1.5*PI;
	if(y==0) return (x>0)? 0.0:PI;
	double tmp=atan((1.0*y)/(1.0*x));
	if(x<0) return PI+tmp;
	return (y>0)? tmp:(2.0*PI+tmp);
}

void run(){
	int i,j,k;
	scanf("%d",&n);
	m=0;
	for(i=0;i<n;i++){
		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		p[i].t1=getA(X1,Y1);
		p[i].t2=getA(X2,Y2);
		if(p[i].t2 < p[i].t1)
			_swap(p[i].t1,p[i].t2);
		a[m++]=p[i].t1;
		a[m++]=p[i].t2;
		if(p[i].t2-p[i].t1 > PI){
			//printf("    %lf %lf\n",p[i].t1,p[i].t2);
			p[i].t1+=2.0*PI;
			a[m++]=p[i].t1;
			_swap(p[i].t1,p[i].t2);
		}
	}
	sort(a,a+m);
	//for(i=0;i<m;i++) printf("%lf\n",a[i]);
	//for(i=0;i<n;i++) printf("%lf %lf\n",p[i].t1,p[i].t2);
	for(i=1;i<=n;i++) cnt[i]=0.0;
	for(i=0;i<m-1;i++){
		int c=0;
		for(j=0;j<n;j++) if(fabs(a[i+1]-a[i])>eps){
			if(p[j].t1<=a[i] && a[i+1]<=p[j].t2)
				c++;
		}
		cnt[c]+=a[i+1]-a[i];
	}
	double ret=0.0;
	for(i=1;i<=n;i++){
		ret+=(1.0*i)*cnt[i]/(2*PI);
	}
	printf("%.5lf\n",ret);
}

void preSof(){
}

int main(){
    //freopen("inputxt","r",stdin);
    //freopen("outputxt","w",stdout);
    preSof();
    //run();
    //while(~scanf("%d%d",&n,&m)) run();
    for(scanf("%d",&TS);cas<=TS;cas++) run();
    return 0;
}