Submission #3975

#	Time	Username	Problem	Language	Result	Execution time	Memory
3975		cki86201	Lonely mdic (kriii1_L)	C++98	0 / 1	0 ms	2280 KiB

L

#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;
}

• Subtask 1: 0 / 1