QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394339#868. Friendship CirclesNahidameowWA 69ms4240kbC++206.7kb2024-04-20 13:11:132024-04-20 13:11:13

Judging History

This is the latest submission verdict.

  • [2024-04-20 13:11:13]
  • Judged
  • Verdict: WA
  • Time: 69ms
  • Memory: 4240kb
  • [2024-04-20 13:11: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 long double eps=1e-4;
namespace GeoDouble{
	typedef long double 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(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<long double,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++)std::cin>>v[i].x>>v[i].y;
	ve<Line>L;
	vec Cor[4]={vec(-1e12,1e12),vec(-1e12,-1e12),vec(1e12,-1e12),vec(1e12,1e12)};
	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: 1ms
memory: 4040kb

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: -100
Wrong Answer
time: 69ms
memory: 4240kb

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:

wrong answer 4961st numbers differ - expected: '3', found: '2'