QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686537 | #685. Y-Shaped Knife | Crysfly | WA | 2ms | 9328kb | C++14 | 3.3kb | 2024-10-29 14:06:24 | 2024-10-29 14:06:25 |
Judging History
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;
}
详细
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)