#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
#define SZ(V) ((int)((V).size()))
using namespace std;
class station {
public:
int M, L, U;
int x, y;
int r[20];
int s[20], w[20];
} S[20];
int N;
double ABS(double x) {
if (x < 0) return -x;
return x;
}
const int TYPE_INTERSECT = 1;
const int TYPE_END = 2;
const int TYPE_START = 3;
const int UP = 0;
const int DOWN = 1;
const double PI = 3.1415926535897932384626433832795;
const double ep = 1.0e-12;
bool isEqual(double a, double b) {
bool azero = ABS(a) < ep;
bool bzero = ABS(b) < ep;
if (azero && bzero)
return true;
if (azero != bzero)
return false;
double d = ABS(a - b);
return (d*d / ABS(a*b)) < ep;
}
class EVENT {
public:
int type;
double X;
int ai, aj, ad;
int bi, bj, bd;
const bool operator < (const EVENT &e) {
if (ABS(X - e.X) <= ep) {
if (type == e.type) {
return S[ai].r[aj] > S[e.ai].r[e.aj];
}
return type < e.type;
}
return X < e.X;
}
};
int index[20][20][2];
class bogen {
public:
int i, j, d;
double X;
};
bogen list[999];
int lh = 0;
vector<EVENT> Events;
EVENT E;
vector< pair<double, double> > getCircleIntersect(int ax, int ay, int ar, int bx, int by, int br) {
vector< pair<double,double> > res;
int dx = bx - ax;
int dy = by - ay;
int dd = dx*dx + dy*dy;
if (dd == 0)
return res;
if (dd >= (ar + br)*(ar + br))
return res;
double d = sqrt((double)dd);
if (ar + d <= br || br + d <= ar)
return res;
double a, b, c, R;
a = bx - ax;
b = by - ay;
c = br;
R = ar;
double U = R*R + a*a + b*b - c*c;
double A, B, C;
A = 4 * a*a + 4 * b*b;
B = - 4 * a * U;
C = U*U - 4 * b*b*R*R;
double Det = B*B - 4*A*C;
if (isEqual(Det, 0)) Det = 0;
if (Det <= -ep || isEqual(A, 0))
return res;
double pl = sqrt(Det);
double x1 = (-B + pl) / (2 * A);
double x2 = (-B - pl) / (2 * A);
double y1 = 0;
double y2 = 0;
if (!isEqual(x1, x2)) { // b != 0
y1 = (U - 2 * a*x1) / (2 * b);
y2 = (U - 2 * a*x2) / (2 * b);
}
else {
y1 = sqrt(R*R - x1*x1);
y2 = -y1;
}
res.push_back(make_pair(x1 + ax, y1 + ay));
res.push_back(make_pair(x2 + ax, y2 + ay));
return res;
}
double getY(int i, int j, int d, double x) {
double cx =S[i].x, cy = S[i].y, r = S[i].r[j];
if (cx - r < x && x < cx + r) {
double t = sqrt(r*r - (x - cx)*(x - cx));
double sign = (d == UP) ? 1 : -1;
return cy + sign * t;
}
return cy;
}
double getY(bogen &b, double x) {
return getY(b.i, b.j, b.d, x);
}
double getArea(bogen b, double sx, double ex) {
double R = S[b.i].r[b.j];
double sy = getY(b, sx);
double ey = getY(b, ex);
double cx = S[b.i].x;
double cy = S[b.i].y;
double st = atan2(sy - cy, sx - cx);
double et = atan2(ey - cy, ex - cx);
double sign = (b.d == UP) ? 1 : -1;
double dt = sign * (st - et);
while (1) {
if (dt < 0) dt += 2 * PI;
else if (dt >= 2 * PI) dt -= 2 * PI;
else
break;
}
double area_circle = (dt / 2 - cos(dt / 2) * sin(dt / 2)) * R*R;
double area_rect = (ex - sx) * (sy + ey) / 2;
return area_rect + sign * area_circle;
}
bool chk[20][20];
double prob[20], allP;
class PROB{
public:
double p;
int i;
int s;
const bool operator < (const PROB &X)const {
return s < X.s;
}
};
double sol = 0.0;
void PROC_LIST(int p, double x) {
if (p < 0 || p + 1 >= lh)
return;
if (isEqual(list[p].X, x))
return;
bogen upper = list[p + 1];
bogen lower = list[p];
double uArea = getArea(upper, list[p].X, x);
double lArea = getArea(lower, list[p].X, x);
double mx = (x + list[p].X) / 2;
double my = (getY(upper, mx) + getY(lower, mx)) / 2;
double area = uArea - lArea;
if (isEqual(area, 0.0))
return;
for (int i = 0; i <N; i++){
for (int j = 0; j < S[i].M; j++) {
double R = S[i].r[j];
double dx = S[i].x - mx;
double dy = S[i].y - my;
chk[i][j] = (dx*dx + dy*dy <= R*R);
}
}
allP = 1.0;
vector<PROB> P;
PROB o;
for (int i = 0; i < N; i++) {
prob[i] = 1.0;
vector <pair<int, int> > Q;
int all = S[i].U - S[i].L + 1;
int nowLast = S[i].U;
for (int j = 0; j < S[i].M; j++) {
if (chk[i][j]) {
Q.push_back(make_pair(S[i].s[j], S[i].w[j]));
}
}
sort(Q.begin(), Q.end());
reverse(Q.begin(), Q.end());
for (int j = 0; j < SZ(Q); j++) {
int s = Q[j].first;
int w = Q[j].second;
int part = nowLast - w + 1;
if (part > 0) {
o.p = ((double)part / (double)all);
o.i = i;
nowLast = w - 1;
o.s = s;
P.push_back(o);
}
}
}
sort(P.begin(), P.end());
reverse(P.begin(), P.end());
double E = 0.0;
for (int i = 0; i < SZ(P); i++){
o = P[i];
double rp = allP * o.p / prob[o.i];
E += rp * o.s;
allP = allP / prob[o.i];
prob[o.i] -= o.p;
allP = allP * prob[o.i];
}
list[p].X = x;
sol += E * area;
}
void EVENT_PROCESS() {
sort(Events.begin(), Events.end());
lh = 0;
for (int i = 0; i < (int)Events.size(); i++) {
E = Events[i];
if (E.type == TYPE_START) {
int p = 0;
bogen b;
for (p = 0; p < lh; p++) {
b = list[p];
double Y = getY(b, E.X);
if (Y > S[E.ai].y || (isEqual(Y, S[E.ai].y) && list[p].d == UP))
break;
}
PROC_LIST(p - 1, E.X);
for (int j = lh+1; j > p+1; j--) {
list[j] = list[j - 2];
}
b.i = E.ai; b.j = E.aj;
b.d = DOWN;
b.X = E.X;
list[p] = b;
b.d = UP;
list[p+1] = b;
lh+=2;
}
if (E.type == TYPE_END) {
int ui = index[E.ai][E.aj][UP];
int di = index[E.ai][E.aj][DOWN];
PROC_LIST(ui - 1, E.X);
PROC_LIST(ui, E.X);
PROC_LIST(di - 1, E.X);
PROC_LIST(di, E.X);
int tlh = lh;
lh = 0;
for (int j = 0; j < tlh; j++) {
if (j == ui || j == di) continue;
list[lh] = list[j];
lh++;
}
}
if (E.type == TYPE_INTERSECT) {
int plus = -1;
vector<int> I, tI;
for (int ti = i; ti < SZ(Events); ti++) {
EVENT tE = Events[ti];
if (tE.type != TYPE_INTERSECT)
break;
if (!isEqual(E.X, tE.X)) {
break;
}
int ai = index[tE.ai][tE.aj][tE.ad];
int bi = index[tE.bi][tE.bj][tE.bd];
I.push_back(ai);
I.push_back(bi);
plus++;
}
sort(I.begin(), I.end());
tI = I;
I.clear();
for (int x = 0; x < SZ(tI); x++) {
if (x == 0 || tI[x - 1] != tI[x])
I.push_back(tI[x]);
}
int ss = -1, ee = -1;
vector<pair<int, int> > rev;
for (int p = 0; p <= SZ(I); p++) {
int pi = -1;
if (p < SZ(I)) {
pi = I[p];
PROC_LIST(pi - 1, E.X);
PROC_LIST(pi, E.X);
}
if (ss == -1) ss = ee = pi;
else {
if (pi != -1 && isEqual(getY(list[ss], E.X), getY(list[pi], E.X))) {
ee = pi;
}
else {
if (ss != -1) {
rev.push_back(make_pair(ss, ee));
}
ss = ee = pi;
}
}
}
for (int r = 0; r < SZ(rev); r++) {
int s = rev[r].first;
int e = rev[r].second;
int N = e - s + 1;
int hN = N / 2;
for (int t = 0; t < hN; t++) {
bogen tmp = list[s + t];
list[s + t] = list[e - t];
list[e - t] = tmp;
}
for (int t = s; t <= e; t++) {
list[t].X = E.X;
}
}
i += plus;
}
// indexing
for (int j = 0; j < lh; j++) {
bogen b = list[j];
index[b.i][b.j][b.d] = j;
}
}
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
E.ai = i;
scanf("%d %d %d %d %d", &S[i].x, &S[i].y, &S[i].M, &S[i].L, &S[i].U);
for (int j = 0; j < S[i].M; j++) {
E.aj = j;
scanf("%d %d %d", &S[i].r[j], &S[i].s[j], &S[i].w[j]);
E.type = TYPE_START;
E.X = S[i].x - S[i].r[j];
Events.push_back(E);
E.type = TYPE_END;
E.X = S[i].x + S[i].r[j];
Events.push_back(E);
for (int ii = 0; ii < i; ii++) {
if (S[i].x == S[ii].x && S[i].y == S[ii].y)
continue;
for (int jj = 0; jj < S[ii].M; jj++) {
vector<pair<double, double> > P = getCircleIntersect(S[i].x, S[i].y, S[i].r[j], S[ii].x, S[ii].y, S[ii].r[jj]);
if (P.size() == 2) {
for (int k = 0; k < 2; k++) {
double x = P[k].first;
double y = P[k].second;
E.type = TYPE_INTERSECT;
E.X = x;
E.bi = ii;
E.bj = jj;
E.ad = y > S[i].y ? UP : DOWN;
E.bd = y > S[ii].y ? UP : DOWN;
Events.push_back(E);
}
}
}
}
}
}
EVENT_PROCESS();
printf("%.16lf\n", sol);
return 0;
}
Compilation message
In file included from /usr/include/c++/4.6/algorithm:63:0,
from R.cpp:3:
/usr/include/c++/4.6/bits/stl_algo.h: In function '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<EVENT*, std::vector<EVENT> >, _Tp = EVENT]':
/usr/include/c++/4.6/bits/stl_algo.h:2253:70: instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<EVENT*, std::vector<EVENT> >]'
/usr/include/c++/4.6/bits/stl_algo.h:2284:54: instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<EVENT*, std::vector<EVENT> >, _Size = long int]'
/usr/include/c++/4.6/bits/stl_algo.h:5407:4: instantiated from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<EVENT*, std::vector<EVENT> >]'
R.cpp:274:35: instantiated from here
/usr/include/c++/4.6/bits/stl_algo.h:2215:4: error: passing 'const EVENT' as 'this' argument of 'const bool EVENT::operator<(const EVENT&)' discards qualifiers [-fpermissive]
R.cpp: In function 'int main()':
R.cpp:405:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
R.cpp:408:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
R.cpp:411:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
