#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!=0.0){
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!=0.0)
{
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));
}
class Arc{
public:
double lo,hi;
Arc(){lo=0.0;hi=0.0;}
Arc(double lo, double hi):lo(lo),hi(hi){}
bool operator<(const Arc& ot)const{
if(!zero(lo-ot.lo))return lo<ot.lo;
return hi<ot.hi;
}
};
vector<vector<pair<int, Arc>>> arcs;
vector<vector<int>> is_contained;
void init(int n, vector<double>& x, vector<double>& y, vector<double>& r){
is_contained = vector<vector<int>>(n);
rep(i,0,n){
rep(k,0,n){
if(i==k)continue;
double dist=sqrt(sq(x[i]-x[k])+sq(y[i]-y[k]));
if(r[k]>r[i]&&dist<=r[k]-r[i]+eps){
is_contained[i].pb(k);
}
}
}
arcs = vector<vector<pair<int,Arc>>>(n);
rep(i,0,n){
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])){
arcs[i].pb({j,Arc(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])){
arcs[i].pb({j,Arc(theta2,pii)});
arcs[i].pb({j,Arc(0.0,theta1)});
}
}
}
}
}
}
double f(int n,vector<double>& x,vector<double>& y,vector<double>& r, int except_idx=-1){
double ans = 0.0;
rep(i,0,n){
if(i==except_idx||is_contained[i].size()>1||(is_contained[i].size()>0&&is_contained[i][0]!=except_idx)){
continue;
}
vector<pair<double,double>> iPnts{};
rep(j,0,arcs[i].size()){
int idx = arcs[i][j].first;
Arc arc = arcs[i][j].second;
if(idx == except_idx)continue;
iPnts.pb({arc.lo,arc.hi});
}
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];
}
init(n,x,y,r);
double S = f(n,x,y,r);
int cnt=0;
for(int i=0;i<n;++i){
if(zero(S-f(n,x,y,r,i)))++cnt;
}
cout<<cnt;
}
Compilation message (stderr)
L.cpp: In function 'void init(int, std::vector<double>&, std::vector<double>&, std::vector<double>&)':
L.cpp:98:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
98 | 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:99:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
99 | rep(k,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:109:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
109 | 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:110:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
110 | 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: In function 'double f(int, std::vector<double>&, std::vector<double>&, std::vector<double>&, int)':
L.cpp:133:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
133 | 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:139:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
139 | rep(j,0,arcs[i].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:154:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
154 | 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:167:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
167 | 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 time | Memory | Grader output |
|---|
| Fetching results... |
