QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#394344#868. Friendship CirclesNahidameowWA 428ms23920kbC++206.7kb2024-04-20 13:16:352024-04-20 13:16:35

Judging History

This is the latest submission verdict.

  • [2024-04-20 13:16:35]
  • Judged
  • Verdict: WA
  • Time: 428ms
  • Memory: 23920kb
  • [2024-04-20 13:16:35]
  • 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-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'