#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;
struct cir{
cir(){}
cir(double x,double y,double r):x(x),y(y),r(r){}
double x,y,r;
}p[310];
struct point{
point(){}
point(double x,double y):x(x),y(y){}
double x,y;
}in[50000];
int A[50000],B[50000],ni,nj;
bool check[310];
int N,L;
const double EPS = 1e-8;
const double INF = 1e10;
inline double ab(double x){return x>0?x:-x;}
bool insame(double a,double b){return ab(a-b)<EPS;}
point solver(double a,double b,double c)
{
double f=b*b-4*a*c;
if(f+EPS<0)return point(INF,INF);
double x = -b/2/a;
double y = sqrt(f)/2/a;
return point(x+y,x-y);
}
double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
void inter(cir a,cir b)
{
double al = 2.0*(b.x-a.x);
double be = 2.0*(b.y-a.y);
double ga = -(a.r*a.r-b.r*b.r-a.x*a.x+b.x*b.x-a.y*a.y+b.y*b.y);
double sq = al*al+be*be;
double xg = 2*al*ga+2*al*be*a.y-2*a.x*be*be;
double sa = be*be*a.x*a.x+(ga+be*a.y)*(ga+be*a.y)-be*be*a.r*a.r;
point tmpx = solver(sq,xg,sa);
if(tmpx.x==INF)return;
point tmpy;
if(insame(tmpx.x,tmpx.y))tmpy = solver(1,-2.0*b.y,b.y*b.y+(tmpx.x-b.x)*(tmpx.x-b.x)-b.r*b.r);
else{
tmpy.x=-(al*tmpx.x+ga)/be;
tmpy.y=-(al*tmpx.y+ga)/be;
}
in[++L]=point(tmpx.x,tmpy.x);
A[L]=ni;B[L]=nj;
in[++L]=point(tmpx.y,tmpy.y);
A[L]=ni;B[L]=nj;
}
bool isin(cir a,point b)
{
double f = dis(point(a.x,a.y),b);
if(f>a.r+EPS)return true;
return false;
}
int main()
{
scanf("%d",&N);
int i;
for(i=1;i<=N;i++)scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
int j;
for(i=2;i<=N;i++){
for(j=1;j<i;j++){
ni=i,nj=j;
inter(p[i],p[j]);
}
}
for(i=1;i<=L;i++){
bool flag=0;
for(j=1;j<=N;j++){
if(j==A[i] || j==B[i])continue;
if(!isin(p[j],in[i])){flag=1;break;}
}
if(!flag)check[A[i]]=check[B[i]]=1;
}
int ans=0;
for(i=1;i<=N;i++){
if(!check[i])ans++;
}
printf("%d",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
