2 条题解
-
0lemontree712 LV 10 @ 2014-01-27 21:04:23
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const double eps = 1e-08;
const double invalid = 1e+50;
const double pi = 3.14159265358979;
inline bool valid (double a)
{
if (a < 1e+40) return true;
else return false;
}
inline int fi (double a)
{
if (a > eps) return 1;
else if (a >= -eps) return 0;
else return -1;
}
inline double ssqrt (double x)
{
if (fi(x) <= 0) return 0;
else return sqrt(x);
}
inline double sacos (double x)
{
if (fi(x + 1) <= 0) return pi;
else if (fi(x - 1) >= 0) return 0;
else return acos(x);
}
double nul (double x, double x0, double r) { return 0; }
double cir (double x, double x0, double r) { return ssqrt(r * r - (x - x0) * (x - x0)); }
double lin (double x, double k, double b) { return k * x + b; }
typedef pair<double, double> prd;
prd bin (double a, double b, double c)
{
double delta = b * b - 4 * a * c;
if (fi(delta) == -1) return prd(invalid, invalid);
else return prd((-b + ssqrt(delta)) / (2 * a), (-b - ssqrt(delta)) / (2 * a));
}
double prlarea (double x0, double r, double x)
{
double st = sacos((x0 - x) / r);
return (st - sin(st * 2) / 2) * (r * r / 2);
}
class segment
{
public:
double k, b, l, r;
segment (void) {}
segment (double x0, double y0, double x1, double y1)
{
k = (y1 - y0) / (x1 - x0);
b = y0 - k * x0;
l = min(x0, x1), r = max(x0, x1);
}
bool online (double x) const { return fi(l - x) <= 0 && fi(x - r) <= 0; }
double intersect (const segment& s) const
{
double ans = (s.b - b) / (k - s.k);
if (online(ans) && s.online(ans)) return ans;
else return invalid;
}
};
class circle
{
public:
double x, r;
circle (void) {}
circle (double x0, double r0) : x(x0), r(r0) {}
double intersect (const circle& c) const
{
if (fi(fabs(c.x - x) - (c.r + r)) >= 0) return invalid;
else if (fi(fabs(c.x - x) - fabs(c.r - r) <= 0)) return invalid;
else return ((r * r - x * x) - (c.r * c.r - c.x * c.x)) / (2 * c.x - 2 * x);
}
prd intersect (const segment& s) const
{
prd ans = bin(1 + s.k * s.k, 2 * s.k * s.b - 2 * x, s.b * s.b + x * x - r * r);
if (valid(ans.first)) if (!s.online(ans.first)) ans.first = invalid;
if (valid(ans.second)) if (!s.online(ans.second)) ans.second = invalid;
return ans;
}
segment cmtangent (const circle& c) const
{
double ca = (r - c.r) / (c.x - x);
double sa = ssqrt(1 - ca * ca);
return segment(x + r * ca, r * sa, c.x + c.r * ca, c.r * sa);
}
};
class func
{
private:
double (*f)(double, double, double);
double arg1, arg2;
public:
func (void) : f(nul) {}
func (const segment& a) : f(lin), arg1(a.k), arg2(a.b) {}
func (const circle& a) : f(cir), arg1(a.x), arg2(a.r) {}
double value (double x) { return (*f)(x, arg1, arg2); }
double weiss (double a, double b)
{
if (f == nul) return 0;
else if (f == cir) return prlarea(arg1, arg2, b) - prlarea(arg1, arg2, a);
else return (value(b) + value(a)) * (b - a) / 2;
}
};
class interval
{
public:
double l, r;
func f;
interval (void) {}
interval (double l0, double r0) : l(l0), r(r0) {}
void load (func ff)
{
int t;
if (t = fi(ff.value(l) - f.value(l)))
{
if (t == 1) f = ff;
return;
}
else if (t = fi(ff.value(r) - f.value(r)))
{
if (t == 1) f = ff;
return;
}
t = fi(ff.value((l + r) / 2) - f.value((l + r) / 2));
if (t == 1) f = ff;
}
double area (void) { return f.weiss(l, r); }
};
circle cs[510]; segment gs[510];
double lsh[500010], lsht[500010]; int lshmr;
interval lqr[500010];
void lshinit (void)
{
sort(lsh, lsh + lshmr);
int cnt = 0;
for (int i = 0; i < lshmr; i++)
{
if (i == 0 || fi(lsh[i] - lsh[i - 1]))
lsht[cnt++] = lsh[i];
} lshmr = cnt;
}
int place (double a)
{
int st = 0, ed = lshmr, mid = 0;
while (ed - st > 1)
{
mid = (st + ed) >> 1;
if (fi(lsht[mid] - a) > 0) ed = mid;
else st = mid;
} return st;
}
int main ()
{
int n, st, ed; double alpha, h[510], r[510], x, ans;
prd res; segment s;
scanf("%d %lf", &n, &alpha); n++;
for (int i = 0; i < n; i++) scanf("%lf", &h[i]);
for (int i = 0; i < n - 1; i++) scanf("%lf", &r[i]);
for (int i = 1; i < n; i++) h[i] += h[i - 1];
for (int i = 0; i < n - 1; i++)
{
x = h[i] / tan(alpha);
cs[i] = circle(x, r[i]);
}
cs[n - 1] = circle(h[n - 1] / tan(alpha), 0);
for (int i = 0; i < n - 1; i++)
{
if (fi(fabs(cs[i].x - cs[i + 1].x) - fabs(cs[i].r - cs[i + 1].r)) == 1)
{
s = cs[i].cmtangent(cs[i + 1]);
gs[i] = s;
}
}
lshmr = 0;
for (int i = 0; i < n - 1; i++)
{
lsh[lshmr++] = cs[i].x - cs[i].r;
lsh[lshmr++] = cs[i].x + cs[i].r;
}
lsh[lshmr++] = cs[n - 1].x;
for (int i = 0; i < n - 1; i++)
{
lsh[lshmr++] = gs[i].l;
lsh[lshmr++] = gs[i].r;
}
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
x = cs[i].intersect(cs[j]);
if (valid(x)) lsh[lshmr++] = x;
}
for (int j = 0; j < n - 1; j++)
{
res = cs[i].intersect(gs[j]);
if (valid(res.first)) lsh[lshmr++] = res.first;
if (valid(res.second)) lsh[lshmr++] = res.second;
}
}
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
x = gs[i].intersect(gs[j]);
if (valid(x)) lsh[lshmr++] = x;
}
}
lshinit();
for (int i = 0; i < lshmr - 1; i++)
lqr[i] = interval(lsht[i], lsht[i + 1]);
for (int i = 0; i < n - 1; i++)
{
st = place(cs[i].x - cs[i].r);
ed = place(cs[i].x + cs[i].r);
for (int j = st; j < ed; j++)
lqr[j].load(func(cs[i]));
}
for (int i = 0; i < n - 1; i++)
{
st = place(gs[i].l);
ed = place(gs[i].r);
for (int j = st; j < ed; j++)
lqr[j].load(func(gs[i]));
}
ans = 0;
for (int i = 0; i < lshmr - 1; i++)
ans += lqr[i].area();
printf("%.2f\n", ans * 2);
return 0;
} -
02014-01-27 21:01:51@
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const double eps = 1e-08;
const double invalid = 1e+50;
const double pi = 3.14159265358979;
inline bool valid (double a)
{
if (a < 1e+40) return true;
else return false;
}
inline int fi (double a)
{
if (a > eps) return 1;
else if (a >= -eps) return 0;
else return -1;
}
inline double ssqrt (double x)
{
if (fi(x) <= 0) return 0;
else return sqrt(x);
}
inline double sacos (double x)
{
if (fi(x + 1) <= 0) return pi;
else if (fi(x - 1) >= 0) return 0;
else return acos(x);
}
double nul (double x, double x0, double r) { return 0; }
double cir (double x, double x0, double r) { return ssqrt(r * r - (x - x0) * (x - x0)); }
double lin (double x, double k, double b) { return k * x + b; }
typedef pair<double, double> prd;
prd bin (double a, double b, double c)
{
double delta = b * b - 4 * a * c;
if (fi(delta) == -1) return prd(invalid, invalid);
else return prd((-b + ssqrt(delta)) / (2 * a), (-b - ssqrt(delta)) / (2 * a));
}
double prlarea (double x0, double r, double x)
{
double st = sacos((x0 - x) / r);
return (st - sin(st * 2) / 2) * (r * r / 2);
}
class segment
{
public:
double k, b, l, r;
segment (void) {}
segment (double x0, double y0, double x1, double y1)
{
k = (y1 - y0) / (x1 - x0);
b = y0 - k * x0;
l = min(x0, x1), r = max(x0, x1);
}
bool online (double x) const { return fi(l - x) <= 0 && fi(x - r) <= 0; }
double intersect (const segment& s) const
{
double ans = (s.b - b) / (k - s.k);
if (online(ans) && s.online(ans)) return ans;
else return invalid;
}
};
class circle
{
public:
double x, r;
circle (void) {}
circle (double x0, double r0) : x(x0), r(r0) {}
double intersect (const circle& c) const
{
if (fi(fabs(c.x - x) - (c.r + r)) >= 0) return invalid;
else if (fi(fabs(c.x - x) - fabs(c.r - r) <= 0)) return invalid;
else return ((r * r - x * x) - (c.r * c.r - c.x * c.x)) / (2 * c.x - 2 * x);
}
prd intersect (const segment& s) const
{
prd ans = bin(1 + s.k * s.k, 2 * s.k * s.b - 2 * x, s.b * s.b + x * x - r * r);
if (valid(ans.first)) if (!s.online(ans.first)) ans.first = invalid;
if (valid(ans.second)) if (!s.online(ans.second)) ans.second = invalid;
return ans;
}
segment cmtangent (const circle& c) const
{
double ca = (r - c.r) / (c.x - x);
double sa = ssqrt(1 - ca * ca);
return segment(x + r * ca, r * sa, c.x + c.r * ca, c.r * sa);
}
};
class func
{
private:
double (*f)(double, double, double);
double arg1, arg2;
public:
func (void) : f(nul) {}
func (const segment& a) : f(lin), arg1(a.k), arg2(a.b) {}
func (const circle& a) : f(cir), arg1(a.x), arg2(a.r) {}
double value (double x) { return (*f)(x, arg1, arg2); }
double weiss (double a, double b)
{
if (f == nul) return 0;
else if (f == cir) return prlarea(arg1, arg2, b) - prlarea(arg1, arg2, a);
else return (value(b) + value(a)) * (b - a) / 2;
}
};
class interval
{
public:
double l, r;
func f;
interval (void) {}
interval (double l0, double r0) : l(l0), r(r0) {}
void load (func ff)
{
int t;
if (t = fi(ff.value(l) - f.value(l)))
{
if (t == 1) f = ff;
return;
}
else if (t = fi(ff.value(r) - f.value(r)))
{
if (t == 1) f = ff;
return;
}
t = fi(ff.value((l + r) / 2) - f.value((l + r) / 2));
if (t == 1) f = ff;
}
double area (void) { return f.weiss(l, r); }
};
circle cs[510]; segment gs[510];
double lsh[500010], lsht[500010]; int lshmr;
interval lqr[500010];
void lshinit (void)
{
sort(lsh, lsh + lshmr);
int cnt = 0;
for (int i = 0; i < lshmr; i++)
{
if (i == 0 || fi(lsh[i] - lsh[i - 1]))
lsht[cnt++] = lsh[i];
} lshmr = cnt;
}
int place (double a)
{
int st = 0, ed = lshmr, mid = 0;
while (ed - st > 1)
{
mid = (st + ed) >> 1;
if (fi(lsht[mid] - a) > 0) ed = mid;
else st = mid;
} return st;
}
int main ()
{
int n, st, ed; double alpha, h[510], r[510], x, ans;
prd res; segment s;
scanf("%d %lf", &n, &alpha); n++;
for (int i = 0; i < n; i++) scanf("%lf", &h[i]);
for (int i = 0; i < n - 1; i++) scanf("%lf", &r[i]);
for (int i = 1; i < n; i++) h[i] += h[i - 1];
for (int i = 0; i < n - 1; i++)
{
x = h[i] / tan(alpha);
cs[i] = circle(x, r[i]);
}
cs[n - 1] = circle(h[n - 1] / tan(alpha), 0);
for (int i = 0; i < n - 1; i++)
{
if (fi(fabs(cs[i].x - cs[i + 1].x) - fabs(cs[i].r - cs[i + 1].r)) == 1)
{
s = cs[i].cmtangent(cs[i + 1]);
gs[i] = s;
}
}
lshmr = 0;
for (int i = 0; i < n - 1; i++)
{
lsh[lshmr++] = cs[i].x - cs[i].r;
lsh[lshmr++] = cs[i].x + cs[i].r;
}
lsh[lshmr++] = cs[n - 1].x;
for (int i = 0; i < n - 1; i++)
{
lsh[lshmr++] = gs[i].l;
lsh[lshmr++] = gs[i].r;
}
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
x = cs[i].intersect(cs[j]);
if (valid(x)) lsh[lshmr++] = x;
}
for (int j = 0; j < n - 1; j++)
{
res = cs[i].intersect(gs[j]);
if (valid(res.first)) lsh[lshmr++] = res.first;
if (valid(res.second)) lsh[lshmr++] = res.second;
}
}
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
x = gs[i].intersect(gs[j]);
if (valid(x)) lsh[lshmr++] = x;
}
}
lshinit();
for (int i = 0; i < lshmr - 1; i++)
lqr[i] = interval(lsht[i], lsht[i + 1]);
for (int i = 0; i < n - 1; i++)
{
st = place(cs[i].x - cs[i].r);
ed = place(cs[i].x + cs[i].r);
for (int j = st; j < ed; j++)
lqr[j].load(func(cs[i]));
}
for (int i = 0; i < n - 1; i++)
{
st = place(gs[i].l);
ed = place(gs[i].r);
for (int j = st; j < ed; j++)
lqr[j].load(func(gs[i]));
}
ans = 0;
for (int i = 0; i < lshmr - 1; i++)
ans += lqr[i].area();
printf("%.2f\n", ans * 2);
return 0;
}
- 1
信息
- ID
- 1839
- 难度
- 5
- 分类
- (无)
- 标签
- 递交数
- 96
- 已通过
- 35
- 通过率
- 36%
- 被复制
- 2
- 上传者