比赛 ZLXSCDay1 评测结果 AAAATTTAAAAAATTAAAAATTTAAAAATTT
题目名称 最小距离和 最终得分 64
用户昵称 Rapiz 运行时间 62.612 s
代码语言 C++ 内存使用 0.39 MiB
提交时间 2016-03-19 11:03:12
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct P{
	int x,y;
	bool operator<(const P& rhs)const{
		return this->x<rhs.x;
	}
};
const int MAXN=10000;
int n;
double ans=0x7f7f7f7f;
P p[MAXN];
double workx(int x){
	double res=0;
	for(int i=0;i<n;i++) res+=abs(p[i].x-x);
	return res;
}
double worky(int y){
	double res=0;
	for(int i=0;i<n;i++) res+=abs(p[i].y-y);
	return res;
}
double workxy(const P& p1,const P& p2){
	double res=0,a=(p1.x-p2.x),b=-(p1.y-p2.y),c=-p1.y*(p1.x-p2.x)+p1.x*(p1.y-p2.y);
	//cout<<a<<' '<<b<<' '<<c<<' ';
	double fenmu=sqrt(a*a+b*b);
	for(int i=0;i<n;i++) res+=abs(a*p[i].y+b*p[i].x+c)/fenmu;
	return res;
}
int main(){
	freopen("space.in","r",stdin);
	freopen("space.out","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y;
	//sort(p,p+n);
	P& mid=p[n/2];
	/*for(int i=0;i<n;i++) if(i!=n/2){
		if(mid.x==p[i].x) ans=min(workx(mid.x),ans);
		else if(mid.y==p[i].y) ans=min(worky(mid.y),ans);
		else ans=min(ans,workxy(mid,p[i]));
	}*/
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j){
		if(p[j].x==p[i].x) ans=min(workx(p[j].x),ans);
		else if(p[j].y==p[i].y) ans=min(worky(p[j].y),ans);
		else ans=min(ans,workxy(p[j],p[i]));
	}
	cout.setf(ios::fixed);
	cout.precision(2);
	cout<<ans;
}