比赛 |
防止浮躁的小练习v0.3 |
评测结果 |
AAAAAAAAAA |
题目名称 |
YL杯超级篮球赛 |
最终得分 |
100 |
用户昵称 |
Rapiz |
运行时间 |
0.191 s |
代码语言 |
C++ |
内存使用 |
2.33 MiB |
提交时间 |
2016-10-12 21:24:18 |
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define file(x) "ballc."#x
using std::sort;
const int MAXN=5e4+10;
int n;
struct P{double x,y,w;}p[MAXN];
bool cmpx(const P& a,const P& b){return a.x<b.x;}
bool cmpy(const P& a,const P& b){return a.y<b.y;}
double ax,ay,ansx=1e30,ansy=1e30,w[MAXN],x[MAXN],y[MAXN];
double calc(double nx,double ny){
double now=0;
for(int j=1;j<=n;j++)
now+=(fabs(nx-p[j].x)+fabs(ny-p[j].y))*p[j].w;
return now;
}
int main(){
freopen(file(in),"r",stdin);
freopen(file(out),"w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf",&p[i].w);
for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) calc(p[i].x,p[j].y);
sort(p+1,p+1+n,cmpx);
for(int i=1;i<=n;i++){
w[i]=w[i-1]+p[i].w;
x[i]=x[i-1]+p[i].x*p[i].w;
}
for(int i=1;i<=n;i++){
double tx=p[i].x,nans=w[i-1]*tx-x[i-1]+(x[n]-x[i])-(w[n]-w[i])*tx;
if(nans<ansx){
ansx=nans;
}
}
sort(p+1,p+1+n,cmpy);
for(int i=1;i<=n;i++){
w[i]=w[i-1]+p[i].w;
y[i]=y[i-1]+p[i].y*p[i].w;
}
for(int i=1;i<=n;i++){
double ty=p[i].y,nans=w[i-1]*ty-y[i-1]+(y[n]-y[i])-(w[n]-w[i])*ty;
if(nans<ansy){
ansy=nans;
}
}
printf("%.2lf",ansy+ansx);
}