记录编号	81510	评测结果	AAAAAAAAAAAA
题目名称	约翰的电网	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.357 s
提交时间	2013-11-14 20:55:02	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#include<cstring>
using namespace std;
#define DVN 100
const int SIZEF=151;
const double INF=1e16;
double minx=INF,miny=INF,maxx=0,maxy=0;
int F;
class POINT{
public:
	double x,y;
	void input(void){
		scanf("%lf%lf",&x,&y);
		x*=10,y*=10;
		minx=min(minx,x);
		miny=min(miny,y);
		maxx=max(maxx,x);
		maxy=max(maxy,y);
	}
};
bool operator < (POINT a,POINT b){
	if(a.x<b.x) return true;
	if(a.x>b.x) return false;
	return a.y<b.y;
}
POINT average(POINT &a,POINT &b){
	return (POINT){(a.x+b.x)/2,(a.y+b.y)/2};
}
void swap(POINT &a,POINT &b){
	POINT c;
	c=a,a=b,b=c;
}
class SEGMENT{
public:
	POINT p1,p2;//p1是坐标小者,p2是大者
	int type;//0是横,1是竖
	void input(void){
		p1.input();
		p2.input();
		if(p2<p1) swap(p1,p2);
		if(p1.x==p2.x) type=1;
		else type=0;
	}
};
double psdist(POINT &a,SEGMENT &b){
	double h,len;
	if(b.type==0){//线段横
		h=fabs(a.y-b.p1.y);
		if(a.x<b.p1.x) len=b.p1.x-a.x;
		else if(a.x>b.p2.x) len=a.x-b.p2.x;
		else len=0;
		return sqrt(h*h+len*len);
	}
	else{//线段竖
		h=fabs(a.x-b.p1.x);
		if(a.y<b.p1.y) len=b.p1.y-a.y;
		else if(a.y>b.p2.y) len=a.y-b.p2.y;
		else len=0;
		return sqrt(h*h+len*len);
	}
}
SEGMENT seg[SIZEF];
POINT ans;
double anssum=INF;
double getsum(POINT a){
	double sum=0;
	int i;
	for(i=1;i<=F;i++){
		sum+=psdist(a,seg[i]);
	}
	return sum;
}
class RECT{//保证是正方形
public:
	POINT min,max;
	double ls;//边长即精度
	double sum;
	double rpsum(void);
	void search(void);
};
bool operator < (RECT &a,RECT &b){
	return a.sum<b.sum;
}
double RECT::rpsum(){
	POINT mid=average(min,max);
	return getsum(mid);
}
void RECT::search(){
	if(ls<=1e-2){
		ans=average(min,max);
		anssum=sum;
		return;
	}
	double step;
	step=ls/(double)DVN;
	double i,j;
	RECT best;
	best.sum=INF;
	RECT now;
	for(i=min.x;i<=max.x-step;i+=step){
		for(j=min.y;j<=max.y-step;j+=step){
			now.min.x=i,now.min.y=j;
			now.max.x=i+step,now.max.y=j+step;
			now.sum=now.rpsum();
			if(now<best) best=now;
		}
	}
	best.ls=step;
	best.search();
}
void work(void){
	RECT now;
	now.min.x=minx,now.min.y=miny;
	now.ls=max(maxx-minx,maxy-miny);
	now.max.x=now.min.x+now.ls,now.max.y=now.min.y+now.ls;
	now.search();
	ans.x/=10,ans.y/=10,anssum/=10;
	printf("%.1lf %.1lf %.1lf\n",ans.x,ans.y,anssum);
}
void read(void){
	scanf("%d",&F);
	int i;
	for(i=1;i<=F;i++) seg[i].input();
}
int main(){
	freopen("fence3.in","r",stdin);
	freopen("fence3.out","w",stdout);
	read();
	work();
	return 0;
}