QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394345#868. Friendship CirclesNahidameowWA 531ms42568kbC++206.7kb2024-04-20 13:17:132024-04-20 13:17:14

Judging History

This is the latest submission verdict.

  • [2024-04-20 13:17:14]
  • Judged
  • Verdict: WA
  • Time: 531ms
  • Memory: 42568kb
  • [2024-04-20 13:17:13]
  • Submitted

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;
}




Details

Tip: Click on the bar to expand more detailed information

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'