QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#394344 | #868. Friendship Circles | Nahidameow | WA | 428ms | 23920kb | C++20 | 6.7kb | 2024-04-20 13:16:35 | 2024-04-20 13:16:35 |
Judging History
answer
#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
bool FileIfstream(std::string name){
std::ifstream f(name.c_str());
return f.good();
}
namespace Math{
ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=2e5+10;
const int mod=998244353;
const __float128 eps=1e-5;
namespace GeoDouble{
typedef __float128 DB;
bool equ(DB x,DB y){return fabs(x-y)<=eps;}
int sgn(DB x){return (DB(0)<x)-(x<DB(0));}
namespace VECTOR{
struct vec{
DB x,y;
//=======================================================
vec(){x=y=0;}
vec(DB _x,DB _y){x=_x,y=_y;}
//=======================================================
vec operator + (vec P){return {x+P.x,y+P.y};}
vec operator - (vec P){return {x-P.x,y-P.y};}
vec operator * (DB d){return {x*d,y*d};}
vec operator / (DB d){return {x/d,y/d};}
DB operator | (vec P){return x*P.x+y*P.y;}
DB operator & (vec P){return x*P.y-y*P.x;}
bool operator <(vec P){return y<P.y||(y==P.y&&x<P.x);}
bool operator == (vec P){return equ(x,P.x)&&equ(y,P.y);}
bool operator != (vec P){return !((*this)==P);}
//=======================================================
DB length_Pow(){return x*x+y*y;}
DB length(){return sqrt(length_Pow());}
//vec rotate(DB theta){return {x*cos(theta)-y*sin(theta),x*sin(theta)+y*cos(theta)};}
vec rotate_90(){return {-y,x};}
};
//============================================================
vec operator * (DB d,vec x){return x*d;}
DB dot(vec w,vec t){return w.x*t.x+w.y*t.y;}
DB cross(vec w,vec t){return w.x*t.y-w.y*t.x;}
//============================================================
vec tranlate(vec x,vec y){return x+y;}
DB orient(vec A,vec B,vec C){return (B-A)&(C-A);}
//============================================================
bool isConvex(std::vector<vec> v){
bool hasPos,hasNeg=false;int n=v.size();
for(int i=0;i<n;i++){
auto plc=orient(v[i],v[(i+1)%n],v[(i+2)%n]);
hasPos|=(plc>0);
hasNeg|=(plc<0);
}return !(hasPos&&hasNeg);
}
DB Area(ve<vec>v){
DB ans=0;int L=v.size();
// for(auto &p:v)
// std::cout<<p.x<<' '<<p.y<<'\n';
for(int i=0;i<L;i++)
ans+=(v[i]&v[(i+1)%L]);
return fabs(ans)/2;
}
//=============================================================
struct Line{
vec S;vec v;
//=========================================================
Line(){S=vec();v=vec();}
Line(vec _S,vec _T){S=_S;v=_T-_S;}
//==========================================================
DB Polar(){return atan2(v.y,v.x);}
vec St(){return S;}
vec To(){return S+v;}
bool operator < (Line &P){
return equ(Polar(),P.Polar())?orient(S,P.S,P.S+P.v)>0:Polar()<P.Polar();}
bool operator == (Line P){
return equ(Polar(),P.Polar());}
bool operator != (Line P){
return !((*this)==P);}
};
bool inter(Line l1,Line l2,vec &out){
DB S1=orient(l1.St(),l2.To(),l1.To()),
S2=orient(l1.St(),l2.St(),l1.To());
if(equ(S1,S2))return false;
out=vec((S1*l2.St().x-S2*l2.To().x)/(S1-S2),
(S1*l2.St().y-S2*l2.To().y)/(S1-S2));
return true;
}
ve<vec>HalfArea(ve<Line> L){
sort(all(L));
ve<Line>res;
for(int i=0;i<L.size();i++)
if(res.empty())res.pd(L[i]);
else if(!equ(res.back().Polar(),L[i].Polar()))
res.pd(L[i]);
L=res;
auto down=[&](Line A,Line B,Line C)->bool{
vec U;
assert(inter(B,C,U));
return orient(U,A.St(),A.To())<0;
};
//for(auto &p:L)
// std::cout<<p.St().x<<' '<<p.St().y<<' '<<p.To().x<<' '<<p.To().y<<'\n';
ve<Line>q;
int l=0,r=-1;
for(int i=0;i<L.size();i++){
while(l<r&&down(L[i],q[r],q[r-1]))r--,q.pop_back();
while(l<r&&down(L[i],q[l],q[l+1]))l++;
q.pd(L[i]);r++;//q[++r]=L[i];
// std::cout<<l<<' '<<r<<'\n';
}
while(l<r&&down(q[l],q[r-1],q[r]))r--;
while(l<r&&down(q[r],q[l],q[l+1]))l++;
ve<vec>ans;
for(int i=l;i<r;i++){
vec U;
assert(inter(q[i],q[i+1],U));
ans.pd(U);
}
if(r-l>1){
vec U;
assert(inter(q[r],q[l],U));
ans.pd(U);
}
return ans;
}//input is NiShiZhen,output is NiShiZhen
}
}
using namespace GeoDouble;
using namespace VECTOR;
struct MI{
std::array<DB,3>S;
bool operator < (const MI P)const{
return !equ(S[0],P.S[0])?S[0]<P.S[0]:(!equ(S[1],P.S[1])?S[1]<P.S[1]:(equ(S[2],P.S[2])?false:S[2]<P.S[2]));
}
};
void solve(){
//don't forget to open long long
int n;std::cin>>n;
ve<vec>v(n+1);
for(int i=1;i<=n;i++){
int x,y;std::cin>>x>>y;
v[i]=vec(x,y);
}
ve<Line>L;
vec Cor[4]={vec(-1e14,1e14),vec(-1e14,-1e14),vec(1e14,-1e14),vec(1e14,1e14)};
L.pd(Line(Cor[0],Cor[1]));
L.pd(Line(Cor[1],Cor[2]));
L.pd(Line(Cor[2],Cor[3]));
L.pd(Line(Cor[3],Cor[0]));
std::map<MI,int>mp;
auto insert=[&](vec P1,vec P2,int ind)->void{
DB A,B,C;
if(equ(P1.x,P2.x)){
B=0;A=1;C=P1.x;}
else if(equ(P1.y,P2.y)){
A=0;B=1;C=P1.y;}
else{
A=1;
B=-(P1.x-P2.x)/(P1.y-P2.y);
C=-(A*P1.x+B*P1.y);
//assert(C==(-(A*P2.x+B*P2.y)));
}
mp[{A,B,C}]=ind;
};
auto query=[&](vec P1,vec P2)->int{
DB A,B,C;
if(equ(P1.x,P2.x)){
B=0;A=1;C=P1.x;}
else if(equ(P1.y,P2.y)){
A=0;B=1;C=P1.y;}
else{
A=1;
B=-(P1.x-P2.x)/(P1.y-P2.y);
C=-(A*P1.x+B*P1.y);
}
if(mp.find({A,B,C})==mp.end())
return -1;
else return mp[{A,B,C}];
};
for(int i=2;i<=n;i++){
vec S=v[i]-v[1];
vec MD=(v[1]+v[i])/2;
S=S.rotate_90();
vec P1=MD+S,P2=MD-S;
if(orient(v[1],MD,P1)>0)
L.pd(Line(MD,P1));
else L.pd(Line(MD,P2));
insert(MD,P1,i);
}
vec U;
inter(L[6],L[4],U);
// std::cerr<<U.x<<' '<<U.y<<'\n';
ve<vec>P=HalfArea(L);
// for(auto &p:P)
// std::cerr<<p.x<<' '<<p.y<<'\n';
ve<std::pair<vec,int>>vt;
for(int i=2;i<=n;i++)vt.pd({v[i],i});
sort(all(vt),[&](auto &x,auto &y){return x.first.x<y.first.x;});
ve<int>ans;
int sz=P.size();
for(int i=0;i<sz;i++){
int C=query(P[i],P[(i+1)%sz]);
if(C!=-1)
ans.pd(C);
}
sort(all(ans));ans.erase(unique(all(ans)),ans.end());
std::cout<<ans.size()<<' ';
for(auto &p:ans)
std::cout<<p-1<<' ';
std::cout<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
if(!FileIfstream("IO.in")){
freopen("IO.in","w",stdout);
return 0;
}
freopen("IO.in","r",stdin);
freopen("IO.out","w",stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T=1;
std::cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4128kb
input:
2 4 1 0 3 1 3 -2 7 0 5 0 0 -2 -1 2 2 -2 10 -1 11
output:
2 1 2 3 1 2 3
result:
ok 7 numbers
Test #2:
score: 0
Accepted
time: 278ms
memory: 4288kb
input:
10000 10 132243110 -894263225 -965927366 756806080 -563126858 -401644076 -528090722 -199265042 -184232391 -184423675 -346777300 -583114791 624815460 788278140 543172921 980159251 -143672624 674688477 -393343296 525780596 9 64745555 827730910 -665070184 -152609349 -905275127 -345568169 -949821348 -84...
output:
3 4 5 6 5 1 4 6 7 8 1 1 3 1 2 3 2 2 5 3 1 2 3 6 1 2 3 4 5 6 5 1 2 3 4 9 4 1 2 3 4 6 1 2 3 4 5 9 2 1 2 3 1 4 6 5 2 4 5 6 7 4 1 2 4 5 3 1 2 3 4 1 2 3 6 3 1 6 8 1 1 2 1 2 5 1 3 4 6 7 5 1 2 4 5 6 3 2 3 4 4 1 3 4 7 4 1 3 7 9 3 3 4 5 4 3 4 6 8 5 1 3 4 6 7 3 1 2 3 2 2 3 3 2 5 6...
result:
ok 41282 numbers
Test #3:
score: 0
Accepted
time: 227ms
memory: 4348kb
input:
1000 53 981976744 508887295 -580496145 -368111494 -40659809 382477779 847997458 -445652992 -709716808 -129570248 -313838973 349710333 -876139130 111370588 320646104 -950965389 548578750 -574361293 -799802872 957309031 127037627 -53366027 -477625360 229044322 -283654405 965960603 -83080242 -489998095...
output:
4 34 40 41 47 6 9 14 19 27 32 67 5 30 37 44 46 48 5 20 27 29 30 38 6 8 11 13 18 23 43 4 5 10 13 89 7 17 26 32 52 70 72 80 5 1 2 3 4 5 4 31 52 57 66 7 9 10 14 16 21 26 27 7 1 5 6 8 9 10 11 8 9 21 22 24 26 27 33 37 7 7 9 28 35 54 55 65 4 14 26 30 62 4 1 2 8 11 6 8 14 36 48 51 76 4 14 1...
result:
ok 6180 numbers
Test #4:
score: 0
Accepted
time: 428ms
memory: 4608kb
input:
100 1000 154123590 -195643584 906998887 659267250 -861981209 -248731154 156410684 -366976998 636150181 849111460 212242101 726773347 -441502446 718696955 -726340230 -438559100 523592711 -829247123 -429817421 -907222370 -743602659 503290332 48678284 954678898 819529524 103315724 -803643464 249247717 ...
output:
5 231 574 863 946 983 5 95 148 373 491 578 6 266 533 717 724 732 829 8 8 26 126 416 647 733 734 831 7 209 630 680 725 926 931 980 7 46 203 385 572 759 798 992 5 234 267 322 395 722 5 234 589 597 724 802 7 77 286 508 527 578 629 949 5 210 754 778 829 933 7 76 214 299 300 746 935 951 6 468 ...
result:
ok 706 numbers
Test #5:
score: 0
Accepted
time: 214ms
memory: 4608kb
input:
50 1000 585441498 537521779 -299019164 -926606017 955725480 -237915475 -999645057 192074481 -543154139 -494983865 -509026736 837773604 548176004 89171630 -985096027 659257966 -821797427 -327883708 571023968 785197466 -650635428 138842844 -81541899 267997223 -369325984 38167872 541905647 -15789881 -3...
output:
6 268 310 339 486 653 770 5 211 282 365 411 636 5 123 209 472 585 766 5 254 393 425 798 927 6 210 570 578 641 908 928 6 129 154 513 717 812 933 6 172 377 476 518 532 716 5 143 417 442 754 888 7 107 145 188 390 567 643 710 8 40 367 386 430 508 694 872 901 5 13 62 335 508 750 4 55 378 408 4...
result:
ok 339 numbers
Test #6:
score: 0
Accepted
time: 87ms
memory: 4604kb
input:
20 1000 949240525 985538611 750623973 -891600358 486266434 -795975822 590585910 -31981534 -330952737 -267486074 161784968 -322523021 570490959 -530866569 -87914744 -576652443 -220687519 -57167345 679521862 -251619499 -274604922 -966571426 -225598794 395382053 779474773 -750165705 -52945103 180963514...
output:
6 116 178 389 511 847 863 6 41 218 430 668 804 951 5 520 526 575 818 914 6 100 127 329 412 551 597 5 50 131 256 361 978 9 47 57 383 446 464 523 584 605 683 5 50 77 488 637 998 7 86 186 208 230 364 639 842 5 87 237 383 590 907 4 229 844 870 979 5 99 509 571 760 945 6 101 108 174 571 681 91...
result:
ok 136 numbers
Test #7:
score: 0
Accepted
time: 87ms
memory: 4432kb
input:
20 1000 -167643347 854054751 -950562769 839061824 -534384313 748502955 -829385211 -983764842 744757226 14818109 -309178784 439036722 -196741654 -211072840 -425752933 -499204526 207784396 947337110 847919880 892677446 -982316981 -346423648 -855715476 -942552076 801788630 -174822793 660149118 76138837...
output:
6 227 232 391 636 754 979 6 229 291 542 673 683 944 5 145 279 435 982 997 5 90 279 338 368 567 4 1 279 387 953 7 54 189 281 466 633 919 955 6 112 206 559 683 897 935 6 17 399 853 938 939 968 7 164 232 535 584 629 651 762 9 19 294 331 417 461 654 770 918 919 8 211 401 419 444 571 613 682 95...
result:
ok 146 numbers
Test #8:
score: 0
Accepted
time: 87ms
memory: 4380kb
input:
20 1000 -989559922 -717620596 788441976 9915493 -700259251 292981732 900386772 654386442 965691382 297122291 70114359 55372274 -404165756 373562106 -498749906 723467583 -508967882 -898415332 426383307 331941687 869779472 273724130 -340607967 279322308 529135191 695487416 -626756661 192070132 3863746...
output:
4 182 471 575 904 6 105 212 248 352 535 679 8 50 307 386 464 547 652 909 952 7 27 180 288 485 821 892 962 6 48 297 437 465 782 876 8 17 81 167 409 438 818 918 930 5 267 363 409 808 926 7 157 249 471 659 662 663 941 6 209 276 547 624 914 926 6 212 235 436 447 651 964 5 54 285 444 455 517 4...
result:
ok 140 numbers
Test #9:
score: 0
Accepted
time: 87ms
memory: 4544kb
input:
20 1000 188523502 855928248 -617777470 35544971 279090002 -722348004 630158756 -297396866 891658241 579426473 744374799 -888100686 238667038 693355835 -836588095 505948204 -375463263 106089122 594781325 331014439 721875924 -251352284 174499542 -203836013 551449048 420573432 381304856 -932537711 -440...
output:
7 189 303 443 746 781 871 994 4 218 623 820 902 5 60 476 828 830 894 7 177 274 406 441 443 553 798 5 123 261 428 610 735 6 86 334 443 532 631 846 6 203 360 503 526 582 707 8 127 162 449 678 684 742 834 993 6 171 184 227 521 561 780 6 103 164 264 407 610 670 8 104 112 157 165 174 558 714 76...
result:
ok 143 numbers
Test #10:
score: 0
Accepted
time: 211ms
memory: 8388kb
input:
10 9172 912539639 -412602596 -170683029 -339514159 240423405 682241967 -908332244 -739591132 49189079 245180429 804822663 -237424332 41789403 -94091238 485092068 920876789 -78296892 313466107 964497553 -653082143 385178750 -111453794 -446173892 688484468 -25448547 -246188240 -995961733 -332340305 87...
output:
6 167 2692 3047 6627 6672 8899 5 102 116 149 164 246 7 15 33 57 65 72 84 117 8 791 1421 2972 3641 4168 7769 7781 9159 6 520 917 1123 1445 2028 2378 5 14 1278 2039 2132 2134 8 1760 2053 2143 2198 4090 5070 5152 5491 6 2 5 7 21 29 190 5 203 415 2511 4767 5208 6 536 4092 4527 5721 7536 7759
result:
ok 72 numbers
Test #11:
score: -100
Wrong Answer
time: 261ms
memory: 23920kb
input:
1 51976 218479545 -323200417 138714781 -709381932 -462379498 450920276 -307976979 426884097 -520439495 892377325 -914912579 -171317468 -862054514 -623904272 -933747975 -562729385 -669135197 -807350552 760790512 -527095882 738243496 -806739291 -377065000 -514514972 -219081738 72062649 648396616 -8346...
output:
112 1228 1530 1569 1586 2123 2402 2975 3247 3895 3897 4388 4421 4869 5151 5729 6130 6397 6598 7660 7709 10664 10702 11093 11474 11589 11618 11893 12138 12917 15827 16041 16133 16642 17362 17533 18105 18737 19488 19576 20790 20852 21345 21709 21998 22782 23622 23672 23698 23776 24168 24547 24743 2526...
result:
wrong answer 1st numbers differ - expected: '4', found: '112'