QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#394345 | #868. Friendship Circles | Nahidameow | WA | 531ms | 42568kb | C++20 | 6.7kb | 2024-04-20 13:17:13 | 2024-04-20 13:17:14 |
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-6;
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: 4104kb
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: 277ms
memory: 3976kb
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: 223ms
memory: 4276kb
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: 431ms
memory: 4336kb
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: 208ms
memory: 4540kb
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: 4420kb
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: 4388kb
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: 83ms
memory: 4428kb
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: 4384kb
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: 220ms
memory: 8320kb
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: 0
Accepted
time: 265ms
memory: 24704kb
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:
4 5729 17362 23622 42866
result:
ok 5 number(s): "4 5729 17362 23622 42866"
Test #12:
score: 0
Accepted
time: 200ms
memory: 22876kb
input:
1 39560 86995686 270580137 459311555 564934617 522290767 180692260 -114536095 -792373236 56831984 126446276 -153352835 766482623 -542260784 -696901245 -856300058 720518338 630336553 -638952534 -945169439 765192059 -936576022 -291631782 844809383 -492201115 -493995722 785156870 933854180 43810956 707...
output:
5 69 9765 13467 22962 39047
result:
ok 6 numbers
Test #13:
score: 0
Accepted
time: 239ms
memory: 24480kb
input:
1 47636 -339455470 864360691 189973737 -455716129 -228197753 -89535757 -771352107 -866406376 44168870 800706716 -537017283 854025817 337341457 965260566 -778852141 -851009748 489616815 939510892 -95839790 912255808 -316428244 518443023 361651062 -469887258 376314486 -501748908 -485720959 362492564 8...
output:
5 12279 15431 28553 37024 44937
result:
ok 6 numbers
Test #14:
score: 0
Accepted
time: 181ms
memory: 20700kb
input:
1 35220 -765906626 308398140 -639172594 -621591067 -683718976 785460418 866799177 -645472221 326473052 -230065548 519509756 -503141389 362167890 892263593 443819968 432237974 -210911435 -892091090 -656575549 -940680444 -841504658 -406640955 -416474555 -742540697 -753375305 211345313 -465104610 91239...
output:
5 431 5596 18791 22640 34886
result:
ok 6 numbers
Test #15:
score: 0
Accepted
time: 165ms
memory: 18076kb
input:
1 33050 -897390485 607211398 -908510412 357758186 300951289 220265106 -84984131 -719505361 903744531 149227595 -718930500 434658701 -758229869 554425404 521267885 -284514303 -56663876 981339632 -362535501 911416009 -221356881 108466554 245591317 -720226840 -472999689 -780593170 -179647045 969729701 ...
output:
6 2785 7705 16069 18056 21113 28584
result:
ok 7 numbers
Test #16:
score: 0
Accepted
time: 102ms
memory: 12176kb
input:
1 20634 -764033129 346216144 -882880935 -662892560 -154569934 -609771423 -741800143 -498571206 -813951287 823488035 337596540 -627541208 -438436139 776395727 303748506 -445976981 -757192126 -850262350 781761444 203703949 398790897 623574063 -532534300 -697912983 -747913673 -67498949 -453997992 -7115...
output:
6 1794 2579 11159 11783 18267 20116
result:
ok 7 numbers
Test #17:
score: -100
Wrong Answer
time: 531ms
memory: 42568kb
input:
1 100000 -646797560 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 648...
output:
26 247 3203 5777 15060 22474 23666 30693 33446 37026 53371 55886 56617 58124 66749 66977 69624 69934 74714 76325 78931 84772 88609 88750 90682 91500 94492
result:
wrong answer 1st numbers differ - expected: '5', found: '26'