QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55815#55. 欧几里得距离之和The_Nobody0 32ms4032kbC++1.2kb2022-10-15 10:42:592022-10-15 10:43:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-15 10:43:02]
  • 评测
  • 测评结果:0
  • 用时:32ms
  • 内存:4032kb
  • [2022-10-15 10:42:59]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define Il inline
#define mem(u,v) memset(u,v,sizeof(u))
#define rep(i,a,b) for(ll i=(a),KKK##i=(b);i<=KKK##i;i++)
#define drep(i,a,b) for(ll i=(a),KKK##i=(b);i>=KKK##i;i--)
#define go(u) for(ll i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),puts("")
using namespace std;
Il ll read(){ll sum=0,f=0;char ch=getchar();for(;!isdigit(ch);ch=getchar())f|=(ch=='-');for(;isdigit(ch);ch=getchar())sum=((sum<<1)+(sum<<3)+(ch^48));return f?-sum:sum;}
void write(const ll x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar(x%10+'0');}
char getc(){char c=getchar();while(!isalpha(c))c=getchar();return c;}
#define N 550000
#define E(x) ((x)*(x))
#define Pi acos(-1)
ll n;double x[N],y[N],X[N],ans;
int main(){
	n=read();rep(i,1,n)x[i]=read(),y[i]=read();
	if(n<=2000){
		rep(i,1,n)rep(j,i+1,n)ans+=sqrt((E(x[i]-x[j])+E(y[i]-y[j])));
		printf("%.10lf",ans);
		return 0;
	}
	double dx=Pi*2/200;
	rep(_,0,199){
		double a=(1.0*_+0.5)*dx,s=sin(a),c=cos(a);
		rep(i,1,n)X[i]=x[i]*c-y[i]*s;
		sort(X+1,X+n+1);
		rep(i,1,n)ans+=X[i]*(i-1-(n-i));
	}
	printf("%.10lf",ans/4);
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 32ms
memory: 4032kb

input:

3000
-802420 -321989
227507 956314
-460698 -819834
-479809 -341770
191520 109304
712327 -189558
-578326 -41090
282566 982266
-859119 686756
209058 -23298
-884994 -349898
-11358 182915
-507706 -81622
745434 575941
-374809 139274
810223 367608
960234 -197223
439081 573568
-275182 999306
-583036 -61808...

output:

149387566007835.7812500000

result:

wrong answer 1st numbers differ - expected: '4693148621177.00000', found: '149387566007835.78125', error = '30.83099'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%