比赛 防止浮躁的小练习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);
}