#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
