比赛 |
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;
}