QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686537#685. Y-Shaped KnifeCrysflyWA 2ms9328kbC++143.3kb2024-10-29 14:06:242024-10-29 14:06:25

Judging History

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

  • [2024-10-29 14:06:25]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9328kb
  • [2024-10-29 14:06:24]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

typedef double db;
const db eps=1e-8,pi=3.14159265358979323846;
int sgn(db x){return x<-eps?-1:x>eps;}
int cmp(db a,db b){return sgn(a-b);}

struct P{
	db x,y;
	P(db x=0,db y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(db o){return x*=o,y*=o,*this;}
	P&operator /=(db o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,db b){return a*=b;}
	friend P operator /(P a,db b){return a/=b;}
	friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
	friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
	friend bool operator !=(P a,P b){return !(a==b);}
	friend db operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend db operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	
	P rot(db o){
		db s=sin(o),c=cos(o);
		return P(x*c-y*s,x*s+y*c);
	}
	P rot90(){return P(-y,x);}
	db ang(){return atan2(y,x);}
	db len(){return sqrt(x*x+y*y);}
	db len2(){return x*x+y*y;}
	
	int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
	P unit(){return ((*this))/len();}
	
	void read(){cin>>x>>y;}
	void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
	if(a.half()!=b.half())return a.half()<b.half();
	return sgn(a*b)>0;
}

db dis(P a,P b){return (a-b).len();}
db cross(P a,P b,P c){
	// (a->b)*(a->c)
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
	return sgn(cross(a,b,c));
}

#define maxn 200005
#define inf 0x3f3f3f3f

int n;
db rang;
P a[maxn];
mt19937_64 rnd(time(0));

pair<db,int> p[maxn];
db S=1.0/sqrt(3);
int chk(db mid)
{
//	cout<<"chk "<<mid<<"\n";
	For(i,1,n){
		if(a[i].x<mid) p[i]=mkp(a[i].y-(mid-a[i].x)*S,-1);
		else p[i]=mkp(a[i].y-(a[i].x-mid)*S,1);
	}
//	sort(p+1,p+n+1);
//	For(i,1,n) cout<<p[i].fi<<" "<<p[i].se<<"\n";
	int pos=n/3*2;
	nth_element(p+1,p+pos+1,p+n+1);
	nth_element(p+pos+1,p+pos+2,p+n+1);
	int sum=0;
	For(i,1,pos)sum+=p[i].se;
	if(sum!=0)return sum;
	puts("Yes");
	P tmp=P(mid,(p[pos].fi+p[pos+1].fi)/2);
	tmp=tmp.rot(rang);
	printf("%.12lf %.12lf %.12lf\n",tmp.x,tmp.y,rang);
	exit(0);
}

signed main()
{
	n=read();
	rang=1.0*rnd()/ULLONG_MAX*(2*pi/3);
//	rang=0;
	For(i,1,n)a[i].x=read(),a[i].y=read(),a[i]=a[i].rot(-rang);
//	For(i,1,n)cout<<a[i].x<<" "<<a[i].y<<"\n";
	//puts("---------");
	if(n%3)puts("No"),exit(0);
	db l=-1e7,r=1e7+114514;
	while(1){
		db mid=(l+r)/2;
		int ans=chk(mid);
		if(ans>0) l=mid;
		else r=mid;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7744kb

input:

9
3 -2
-4 6
0 -7
-5 -6
5 1
1 6
-5 0
-3 -7
-4 2

output:

Yes
-1.444026584319 -1.839962569059 1.313536117334

result:

ok Answer is found

Test #2:

score: 0
Accepted
time: 0ms
memory: 8836kb

input:

4
568817 -532765
20585 -88674
54620 539081
866306 368203

output:

No

result:

ok No answer

Test #3:

score: 0
Accepted
time: 0ms
memory: 8464kb

input:

3
-249533 -739397
681290 -376732
-942721 799628

output:

Yes
-344029.194236348500 -500252.528403096600 1.313536117334

result:

ok Answer is found

Test #4:

score: 0
Accepted
time: 2ms
memory: 9264kb

input:

6
303183 -370732
578892 -257778
328641 25259
660987 62586
-949298 876989
-727181 -390642

output:

Yes
60434.930605045141 43305.583294924218 1.313536117334

result:

ok Answer is found

Test #5:

score: 0
Accepted
time: 2ms
memory: 9328kb

input:

9
302505 -89769
578921 395830
-909766 794824
-13472 -33592
837847 825866
807789 -644604
744094 -411512
-358771 287832
173441 563062

output:

Yes
209651.246877454803 4048.263769999852 1.313536117334

result:

ok Answer is found

Test #6:

score: 0
Accepted
time: 0ms
memory: 8204kb

input:

12
-320242 -292874
131803 883484
-757350 840492
684942 -214670
-119683 -815491
-306255 148032
-380136 -770001
-755821 -24754
287075 -924350
650253 -116847
49079 904406
-401048 -482856

output:

Yes
-177896.521217094967 -218976.084468188463 1.313536117334

result:

ok Answer is found

Test #7:

score: 0
Accepted
time: 2ms
memory: 7428kb

input:

15
-954613 -90307
682160 -640829
-459503 521186
372656 -72950
-372296 372397
-208372 596601
-753367 699172
997515 -835228
-7553 367924
-272374 462113
-841743 -231646
-892364 984763
-900507 663513
-780605 -498703
89348 -171558

output:

Yes
-399152.261169393314 164218.374119447777 1.313536117334

result:

ok Answer is found

Test #8:

score: 0
Accepted
time: 0ms
memory: 8784kb

input:

90
-612929 285792
-19561 546583
-639275 -350337
799407 -879779
-43931 -641532
696565 -442617
9217 148356
235427 -401407
867598 158249
998488 -484957
976428 844546
220878 864532
148005 456856
-720917 -426254
566450 -197779
-375805 244999
-610641 225683
245057 -354612
-918669 -124372
344909 501051
943...

output:

Yes
-122565.587734624482 -190371.123640873499 1.313536117334

result:

ok Answer is found

Test #9:

score: 0
Accepted
time: 2ms
memory: 8812kb

input:

102
703172 -902382
166116 -137491
-787848 -847731
461115 -197036
-887051 382441
724936 578216
-881935 -541390
20570 563876
-273641 120215
302538 86089
-201359 -651737
-323457 431538
-18254 249011
-886355 -985155
103593 -501845
926942 -514332
-859052 -232289
-407112 -393917
479637 -264919
-951386 312...

output:

Yes
-119403.532123783894 70307.765123754187 1.313536117334

result:

ok Answer is found

Test #10:

score: 0
Accepted
time: 0ms
memory: 8356kb

input:

201
663725 -492020
591705 581345
-118339 243511
-565704 72686
-741424 419466
437247 -783537
249861 704337
-896935 7304
78089 895958
478112 -416512
-919829 -58995
184146 -341929
-699105 -66226
-29671 -425147
-762888 561875
582909 -935883
236267 -315536
33248 -613691
325560 842947
-540948 33719
430588...

output:

Yes
58181.907101472600 43898.331231520118 1.313536117334

result:

ok Answer is found

Test #11:

score: 0
Accepted
time: 2ms
memory: 8256kb

input:

300
475511 68475
-180117 828757
-773621 255111
444934 -473463
935502 -650554
95466 -239793
252196 620342
-694496 -923056
-372597 -292680
-869227 904582
507988 -241895
-227255 -294402
-944712 524888
364483 650890
886382 -367145
-413100 87857
-518189 -231234
402554 -17402
-226340 -310233
-869500 -9161...

output:

Yes
-85192.994698445778 -40250.274794038582 1.313536117334

result:

ok Answer is found

Test #12:

score: 0
Accepted
time: 2ms
memory: 7532kb

input:

402
-878876 -548660
-943681 -862651
950987 634649
562406 -832920
-916301 -112118
-261500 628797
-370085 -764392
272803 15041
130199 686407
-622556 -984304
33707 313799
-514921 835623
760169 -991536
-200678 710727
114518 939188
319859 454798
-125633 -947592
473610 126528
112927 -315178
206732 -907686...

output:

Yes
-13568.339319384417 -48938.245850174288 1.313536117334

result:

ok Answer is found

Test #13:

score: 0
Accepted
time: 0ms
memory: 8864kb

input:

501
-324676 461718
-745592 534607
-663500 167782
-706073 381621
-634673 192683
-881171 485739
-746219 235719
398001 -362272
-747958 145384
-295364 -923980
244314 606072
37191 -989606
697251 -28583
-191247 526184
-738009 404697
314840 -202704
-213746 -571320
94301 381339
454551 806139
-981612 580215
...

output:

Yes
-47720.008711570219 -9486.006441629987 1.313536117334

result:

ok Answer is found

Test #14:

score: 0
Accepted
time: 2ms
memory: 7380kb

input:

600
-750691 62203
157089 -159472
-86294 -740665
788032 223504
533266 -556786
-344620 -598332
966532 -898609
6239 -52969
-274058 -469807
-259783 455365
742219 -111513
799086 -20503
-520643 -275854
387831 510239
-488155 -955442
-358811 -458125
701162 -278923
624099 490570
-171529 37489
-498049 -283263...

output:

Yes
230.483625731214 22647.511932951926 1.313536117334

result:

ok Answer is found

Test #15:

score: 0
Accepted
time: 2ms
memory: 8864kb

input:

702
-868961 520520
-987170 -353837
532839 -617153
-761583 556933
927846 66237
-416377 586191
-920400 125338
833838 920325
-606657 -577693
-665139 292370
-810833 270249
-113581 -923151
608137 -875241
-920722 -896210
-321479 -251950
-564649 -60708
980194 908971
180112 947031
-85980 -754599
-660518 535...

output:

Yes
-64710.425430545190 -45639.033788553759 1.313536117334

result:

ok Answer is found

Test #16:

score: 0
Accepted
time: 2ms
memory: 7976kb

input:

801
455327 143325
892532 -692761
416434 -754711
-4458 -114828
485238 -734953
-477050 -944180
-256382 -42088
239808 861273
714199 -891958
150869 -847768
747357 -518122
-250638 342590
-882172 -582791
119795 -878996
-428416 -243577
-897704 -695992
-743890 735566
469195 477919
-495109 -337768
797215 968...

output:

Yes
10680.897968711852 -2000.242816633054 1.313536117334

result:

ok Answer is found

Test #17:

score: 0
Accepted
time: 2ms
memory: 9248kb

input:

900
-802763 15
364251 -486580
-168934 230843
-216661 -397179
942920 -591485
163530 -95309
-174388 -934115
890603 -894157
-708749 986248
-580655 442726
424887 -252442
303713 400868
-275863 -293050
-740874 -672671
312844 348981
122478 -522997
78802 380572
749700 869501
681587 -900963
159018 -41354
970...

output:

Yes
-22341.114403191103 -41552.337025206645 1.313536117334

result:

ok Answer is found

Test #18:

score: -100
Wrong Answer
time: 2ms
memory: 7740kb

input:

501
165 -48
-261 -134
-499 -20
-263 -112
-226 -87
-169 441
-82 321
-41 240
55 92
-147 157
-307 178
481 -176
205 -359
-317 -62
-380 -28
252 253
289 -399
-9 367
331 420
448 -329
-166 390
232 169
345 142
12 312
-187 -362
-381 330
-358 152
152 -261
-293 90
-463 212
316 -69
354 486
-351 -282
386 477
483 ...

output:

Yes
3.160422535822 17.403978057509 1.313536117334

result:

wrong answer Incorrect point count (167/168/166)