답안 #19209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19209	2016-02-20T21:18:40 Z	cki86201	Lonely mdic (kriii1_L)	C++	0 / 1	0 ms	2548 KB

L

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

typedef pair<double,double> Pd;
double x[100010];
int xz;
int N;
const double EPS = 1e-13;

struct circle{
	int x, y, r;
	bool operator==(const circle &l)const{
		return x == l.x && y == l.y && r == l.r;
	}
}C[305];

struct point{
	point(){}
	point(double x,double y):x(x),y(y){}
	double x, y;
};

struct lx{
	lx(){}
	lx(double x,int p):p(p),x(x){}
	int p;
	double x;
	bool operator<(const lx &l)const{
		return fabs(x - l.x) < EPS ? p < l.p : x < l.x;
	}
}v[660];

int ans;
int chk[330];
int Left[330], Right[330];
int tv;

int main(){
	scanf("%d", &N);
	rep(i, N){
		scanf("%d%d%d", &C[i].x, &C[i].y, &C[i].r);
		for(int j=0;j<i;j++){
			if(C[i] == C[j]){
				i--; N--; ans++;
				break;
			}
		}
	}
	/*
	 N = 300;
	 rep(i, N){
	 C[i].r = 1000 - i / 100;
	 C[i].x = i % 40 - 20;
	 C[i].y = i / 30 - 15;
	 }
	 */
	rep(i, N)Left[i] = C[i].x - C[i].r, Right[i] = C[i].x + C[i].r;
	rep(i, N)rep(j, i){
		// http://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect
		int x1 = C[i].x, x2 = C[j].x, y1 = C[i].y, y2 = C[j].y;
		int r1 = C[i].r, r2 = C[j].r;
		int lensq = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
		if(lensq < (r1-r2) * (r1-r2))continue;
		if(lensq > (r1+r2) * (r1+r2))continue;
		double d = sqrt(lensq);
		double l = (r1*r1 - r2*r2 + lensq) / (2 * d);
		double h = sqrt(r1*r1 - l*l);
		double g1 = l/d * (x2-x1) + h/d * (y2-y1) + x1;
		double g2 = l/d * (x2-x1) - h/d * (y2-y1) + x1;
		if(lensq == (r1-r2) * (r1-r2) || lensq == (r1+r2) * (r1+r2) || y1 == y2)x[xz++] = g1 - 10*EPS, x[xz++] = g1 + 10*EPS;
		else x[xz++] = g1, x[xz++] = g2;
	}
	rep(i, N){
		x[xz++] = Left[i] + 10*EPS;
		x[xz++] = Right[i] - 10*EPS;
	}
	sort(x, x+xz);
	rep(i, xz){
		if(i == 0 || x[i] - x[i-1] > EPS){
		//	printf("X%f\n", x[i]);
			tv = 0;
			rep(j, N){
				if(Left[j] + EPS < x[i] && x[i] < Right[j] - EPS){
					double y1 = sqrt(C[j].r * C[j].r - (C[j].x - x[i]) * (C[j].x - x[i]));
					double y2 = -y1;
					y1 += C[j].y;
					y2 += C[j].y;
					v[tv++] = lx(y2, j);
					v[tv++] = lx(y1, -j-1);
				}
			}
			sort(v, v + tv);
		//	rep(i, tv)printf("%d %f\n", v[i].p, v[i].x); puts("");
			int now[2] = {};
			rep(j, tv){
				if(v[j].p < 0)now[0]--, now[1] += v[j].p;
				else now[0]++, now[1] += v[j].p+1;
				if(now[0] == 1)chk[now[1]-1] = 1;
			}
		//	rep(j, N)printf("%d ", chk[j]); puts("");
		}
	}
	rep(i, N)if(!chk[i])ans++;
	printf("%d", ans);
	return 0;
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	2548 KB	Output isn't correct
2	Halted	0 ms	0 KB	-