记录编号	171553	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]气场区域	最终得分	100
用户昵称	炎帝	是否通过	通过
代码语言	C++	运行时间	9.939 s
提交时间	2015-07-19 20:16:32	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const double INF=1e8,eps=1e-8,Dnum=1000;
const int SIZEN=60;
#define sqr(x) ((x)*(x))
class Point{
public:
	double x,y;
};
void print(Point p){printf("(%lf %lf)",p.x,p.y);}
inline double dist(Point A,Point B){
	return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
}
inline bool Solve_Quadratic(double a,double b,double c,double &x1,double &x2){//就是解二次方程
	double dlt=b*b-4*a*c;
	if(dlt<0) return false;
	dlt=sqrt(dlt);
	x1=(-b-dlt)/(2*a);
	x2=(-b+dlt)/(2*a);
	if(x1>=x2) swap(x1,x2);
	return true;
}
inline pair<double,double> Intersection(pair<double,double> a,pair<double,double> b){
	return make_pair(max(a.first,b.first),min(a.second,b.second));
}
inline bool Circle_Line_Intersection(double x0,double y0,double r,double t,double &x1,double &x2){
	//圆心(x0,y0)半径r的圆和直线y=t的相交部分
	//方程:(x^2)-(2x0x)+(x0^2)+((b-y0)^2)-(r^2)<=0
	return Solve_Quadratic(1,-2*x0,sqr(x0)+sqr(t-y0)-sqr(r),x1,x2);
}
inline void Segment_Field_Affect(Point A,Point B,double t,vector<pair<double,double> > &V){
	if(dist(A,B)<eps) return;
	//线段AB所产生的气场在直线y=t上的部分,如果有就压入V
	double x1,x2;
	if(Circle_Line_Intersection((A.x+B.x)/2,(A.y+B.y)/2,dist(A,B)/2,t,x1,x2))
		V.push_back(make_pair(x1,x2));
}
inline void Segment_Point_Field_Affect_Single(Point A,Point B,Point C,double t,vector<pair<double,double> > &V){
	//线段AB,点C共同产生的气场在直线y=t上的部分,这里只考虑AB的一个方向,如果有就压入V
	double x1,x2,x3=INF,x4=-INF;
	if(!Solve_Quadratic(1,-(A.x+C.x),A.x*C.x-(t-C.y)*(A.y-t),x1,x2)) return;
	Solve_Quadratic(1,-(B.x+C.x),B.x*C.x-(t-C.y)*(B.y-t),x3,x4);//如果求解失败,x3=INF和x4=-INF并未改变
	V.push_back(Intersection(make_pair(x1,x2),make_pair(-INF,x3)));
	V.push_back(Intersection(make_pair(x1,x2),make_pair(x4,INF)));
}
inline void Segment_Point_Field_Affect(Point A,Point B,Point C,double t,vector<pair<double,double> > &V){
	if(dist(A,B)<eps) return;
	Segment_Point_Field_Affect_Single(A,B,C,t,V);
	Segment_Point_Field_Affect_Single(B,A,C,t,V);
}
inline void Segment_Segment_Field_Affect(Point A,Point B,Point C,Point D,double t,vector<pair<double,double> > &V){
	Segment_Point_Field_Affect(A,B,C,t,V);
	Segment_Point_Field_Affect(A,B,D,t,V);
	Segment_Point_Field_Affect(C,D,A,t,V);
	Segment_Point_Field_Affect(C,D,B,t,V);
}
int N;
double Xmax,Ymax;
Point seg[SIZEN][2];
inline double Calc_Quiet_Len(double t){
	static vector<pair<double,double> > cov;
	cov.clear();
	for(int i=1;i<=N;i++) Segment_Field_Affect(seg[i][0],seg[i][1],t,cov);
	for(int i=1;i<=N;i++)
		for(int j=1;j<i;j++)
			Segment_Segment_Field_Affect(seg[i][0],seg[i][1],seg[j][0],seg[j][1],t,cov);
	sort(cov.begin(),cov.end());
	double now=0,ans=0;
	for(int i=0;i<cov.size();i++){
		if(cov[i].first>Xmax) break;
		if(cov[i].first>now) ans+=cov[i].first-now;
		now=max(now,cov[i].second);
	}
	if(now<=Xmax) ans+=Xmax-now;
	return ans;
}
void Process(void){
	double d=Ymax/Dnum,ans=0;
	for(int i=0;i<Dnum;i++)	ans+=d*Calc_Quiet_Len(d*i);
	printf("%lf\n",ans/(Xmax*Ymax));
}
void Read(void){
	scanf("%d",&N);
	scanf("%lf%lf",&Xmax,&Ymax);
	for(int i=1;i<=N;i++) scanf("%lf%lf%lf%lf",&seg[i][0].x,&seg[i][0].y,&seg[i][1].x,&seg[i][1].y);
}
int main(){
	freopen("nt2011_region.in","r",stdin);
	freopen("nt2011_region.out","w",stdout);
	Read();
	Process();
	return 0;
}