Submission #1279091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279091		gihagay	Lonely mdic (kriii1_L)	C++17	0 / 1	2094 ms	3740 KiB

L

#include <bits/stdc++.h>
#define int long long
using namespace std;

const double pi=acos(-1);

struct circle{
  double x,y,r;
  double arc(double t1,double t2){
    return r*r*(t2-t1)/2+r*(x*(sin(t2)-sin(t1))-y*(cos(t2)-cos(t1)))/2;
  }
};

double acor(double a){
  if(a<0) a+=2*pi;
  if(a<0) a+=2*pi;
  if(a>=2*pi) a-=2*pi;
  if(a>=2*pi) a-=2*pi;
  return a;
}

int n,ans;
double S,S2,x[300],y[300],r[300];
vector<circle> c1,c;

double solve(int idx){
  c1.clear();
  c.clear();
  for(int i=0;i<n;i++){
    if(i!=idx) c1.push_back({x[i],y[i],r[i]});
  }
  int N=c1.size();
  for(int i=0;i<N;i++){
    bool chk=1;
    for(int j=0;j<N;j++){
      if(i==j) continue;
      if(hypot(c1[i].x-c1[j].x,c1[i].y-c1[j].y)<=c1[j].r-c1[i].r){
        chk=0;
        break;
      }
    }
    if(chk){
      c.push_back(c1[i]);
    }
  }
  N=c.size();
  vector<vector<pair<double,int>>> a(N);
  double A,d,am,ap,alpha,ret=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(i==j) continue;
      d=hypot(c[j].x-c[i].x,c[j].y-c[i].y);
      if(d>=c[i].r+c[j].r) continue;
      A=acor(atan2(c[j].y-c[i].y,c[j].x-c[i].x));
      alpha=acos((c[i].r*c[i].r+d*d-c[j].r*c[j].r)/(2*c[i].r*d));
      am=acor(A-alpha),ap=acor(A+alpha);
      if(am<=ap){
        a[i].push_back({am,-1});
        a[i].push_back({ap,1});
      }
      else{
        a[i].push_back({0,-1});
        a[i].push_back({ap,1});
        a[i].push_back({am,-1});
        a[i].push_back({2*pi,1});
      }
    }
    if(a[i].empty()){
      ret+=pi*c[i].r*c[i].r;
      continue;
    }
    a[i].push_back({2*pi,0});
    sort(a[i].begin(),a[i].end());
    int cnt=0;
    double prv=0;
    for(auto [X,D]:a[i]){
      if(cnt==0) ret+=c[i].arc(prv,X);
      cnt+=D;
      prv=X;
    }
  }
  return ret;
};

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>n;
  for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>r[i];
  S=solve(-1);
  for(int i=0;i<n;i++){
    S2=solve(i);
    if(abs(S-S2)<1e-7) ans++;
  }
  cout<<ans;
}

• Subtask 1: 0 / 1