Submission #1274473

#TimeUsernameProblemLanguageResultExecution timeMemory
1274473ddddewangLonely mdic (kriii1_L)C++20
0 / 1
147 ms648 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define rep(i,a,b) for(register int i=a;i<b;++i)
#define per(i,a,b) for(register int i=a;i>b;--i)
#define F first
#define S second
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define mp make_pair
#define full(a) a.begin(),a.end()
#define rfull(a) a.rbegin(),a.rend()

const double pi=acos(-1.0);
const double pii=2*pi;
const double eps=1e-10;

inline double sq(double a){ return a*a;}
inline double norm(double th) {
	while (th < 0) th += pii;
	while (th > pii - eps) th -= pii;
	return th;
}
inline double zero(double a){return abs(a)<eps;}

bool inter(int i,int j,vector<double>& x,vector<double>& y,vector<double>& r){
	double d = sqrt(sq(x[i]-x[j])+sq(y[i]-y[j]));
	if(d>r[i]+r[j] || abs(r[i]-r[j])>=d){
		return false;
	}
	return true;
}

void quadratic(double a,double b,double c,double& x1,double& x2){
	x1 = (-b-sqrt(max(0.0,sq(b)-4*a*c)))/(2*a);
	x2 = (-b+sqrt(max(0.0,sq(b)-4*a*c)))/(2*a);
}

void lyx(double a,double b,double c,double& x, double& y){
	if(b){
		y=(c-a*x)/b;
	}
}

bool lcf(double x,double y,double r,double a,double b, double c,vector<double>& ans){
	double x1,x2,y1,y2;
	if(b)
	{
		quadratic(1+sq(a/b),-2*x-2*(a/b)*(c/b-y),sq(x)+sq(c/b-y)-sq(r),x1,x2);
		lyx(a,b,c,x1,y1);
		lyx(a,b,c,x2,y2);
		ans = {x1,y1,x2,y2};
	}
	else{
		quadratic(1,-2*y,sq(y)+sq(c/a-x)-sq(r),y1,y2);
		x1=c/a;
		ans={x1,y1,x1,y2};
	}
	return true;
}

inline double gth(double x,double y){
	if(x>0.0&&y==0.0){ return 0.0;}
	if(x>0.0&&y>0.0){ return atan(y/x);}
	if(x==0.0&&y>0){ return pi/2.0;}
	if(x<0.0&&y>0.0){ return pi-atan(abs(y/x));}
	if(x<0.0&&y==0.0){ return pi;}
	if(x<0.0&&y<0.0){ return pi+atan(abs(y/x));}
	if(x==0.0&&y<0.0){ return 1.5*pi;}
	if(x>0.0&&y<0.0){ return pii-atan(abs(y/x));}
	return 0.0;
}

inline double f1(double x,double y, double r, double theta){
	return 0.5*(r*(x*sin(theta))-r*(y*cos(theta))+sq(r)*(theta));
}

double f(int n,vector<double> x,vector<double> y,vector<double> r){
	double ans = 0.0;
	rep(i,0,n){
		vector<pair<double,double>> iPnts{};
		rep(j,0,n){
			if(i!=j&&inter(i,j,x,y,r)){
				vector<double> ans(4,0.0);
				lcf(x[i],y[i],r[i],2*(x[j]-x[i]),2*(y[j]-y[i]),sq(r[i])-sq(r[j])+sq(x[j])-sq(x[i])+sq(y[j])-sq(y[i]),ans); // ans = {교점1, 교점2}
				double theta1=gth(ans[0]-x[i],ans[1]-y[i]), theta2=gth(ans[2]-x[i],ans[3]-y[i]); // 교점 좌표로 theta값 구함
				if(theta1>theta2){ swap(theta1,theta2);}
                // always theta2>=theta1
				if(sq(x[j]-x[i]-r[i]*cos((theta1+theta2)/2.0))+sq(y[j]-y[i]-r[i]*sin((theta1+theta2)/2.0))<sq(r[j])){
					iPnts.pb({theta1,theta2});
				}
				else{
					if(sq(x[j]-x[i]-r[i]*cos(norm((theta1+theta2)/2.0+pi)))+sq(y[j]-y[i]-r[i]*sin(norm((theta1+theta2)/2.0+pi)))<sq(r[j])){
						iPnts.pb({theta2,pii});
						iPnts.pb({0.0,theta1});
					}
				}
			}
		}
		if(iPnts.size()==0){
			ans+=pi*sq(r[i]);
		}
		else{
			sort(full(iPnts));
			double theta1=iPnts[0].F,theta2=iPnts[0].S;
			vector<pair<double,double>> intlims{{0.0,theta1}};

			rep(j,0,iPnts.size()){
				while(j<iPnts.size()&&theta2>=iPnts[j].F){ // theta1이 theta2보다 작으면 겹치므로, 구간 합쳐줌
					theta2=max(iPnts[j].S,theta2);
					j++;
				}
				if(j<iPnts.size()){
					intlims.pb({theta2,iPnts[j].F}); // 계산해줘야 하는 부분(즉, 나와있는 부분)의 theta 범위 추가
					theta1=iPnts[j].F;
					theta2=iPnts[j].S;
				}
			}
			intlims.pb({theta2,pii});

			rep(j,0,intlims.size()){
				//cout<<intlims[j].F/pi*180<<' '<<intlims[j].S/pi*180<<'\n';
				if(!(intlims[j].F==0.0&&intlims[j].S==pii)&&(intlims[j].F!=intlims[j].S)){
					ans+=(f1(x[i],y[i],r[i],intlims[j].S)-f1(x[i],y[i],r[i],intlims[j].F));
				}
			}
		}
	}
	return ans;
}

inline bool f4(int j,int i,vector<double>& x,vector<double>& y,vector<double>& r){
	return (j!=i && (sqrt(sq(x[i]-x[j])+sq(y[i]-y[j]))+r[j])<=r[i])? true:false;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;cin>>n;
	vector<double> x(n),y(n),r(n);
	for(int i=0;i<n;++i){
		cin>>x[i]>>y[i]>>r[i];
	}
	double S = f(n,x,y,r);
	int cnt=0;
	for(int i=0;i<n;++i){
	    
        double tmp = r[i];
        r[i] = 0;
		if(zero(S-f(n,x,y,r)))++cnt;
        r[i] = tmp;
	}
	cout<<cnt;
}

Compilation message (stderr)

L.cpp: In function 'double f(int, std::vector<double>, std::vector<double>, std::vector<double>)':
L.cpp:83:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   83 |         rep(i,0,n){
      |             ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
L.cpp:85:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   85 |                 rep(j,0,n){
      |                     ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
L.cpp:111:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  111 |                         rep(j,0,iPnts.size()){
      |                             ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
L.cpp:124:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  124 |                         rep(j,0,intlims.size()){
      |                             ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...