HDu 5130(円と凸多角形の交差面積)
11971 ワード
标题:簡単な多角形、つまり凸多角形があり、現在2つの点AとBがあり、凸多角形上の点P、PからBまでの距離はPからAまでの距離のK倍を超えず、条件を満たすPの領域の面積はいくらですか.问题解:式PA*K>=PBと考えられますが、この问题のポイントは、K<1であるため、この式が円と凸多角形の交差面积であることです.円の一般式:x^2+y^2+Dx+Ey+F=0円の標準方程式:(x-a)^2+(y-b)^2=c^2(a,b)->(-D/2,-E/2)c=sqrt(D*D+E*E-4*F)/2次に円と凸多角形の交差面積テンプレートをセットする.
#include
#include
#include
#include
#include
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1);
int dcmp(double x)
{
if(x > eps) return 1;
return x < -eps ? -1 : 0;
}
struct Point
{
double x, y;
Point(){x = y = 0;}
Point(double a, double b)
{x = a, y = b;}
inline void read()
{scanf("%lf%lf", &x, &y);}
inline Point operator-(const Point &b)const
{return Point(x - b.x, y - b.y);}
inline Point operator+(const Point &b)const
{return Point(x + b.x, y + b.y);}
inline Point operator*(const double &b)const
{return Point(x * b, y * b);}
inline double dot(const Point &b)const
{return x * b.x + y * b.y;}
inline double cross(const Point &b, const Point &c)const
{return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);}
inline double Dis(const Point &b)const
{return sqrt((*this - b).dot(*this - b));}
inline bool InLine(const Point &b, const Point &c)const//
{return !dcmp(cross(b, c));}
inline bool OnSeg(const Point &b, const Point &c)const// ,
{return InLine(b, c) && (*this - c).dot(*this - b) < eps;}
};
inline double min(double a, double b)
{return a < b ? a : b;}
inline double max(double a, double b)
{return a > b ? a : b;}
inline double Sqr(double x)
{return x * x;}
inline double Sqr(const Point &p)
{return p.dot(p);}
Point LineCross(const Point &a, const Point &b, const Point &c, const Point &d)
{
double u = a.cross(b, c), v = b.cross(a, d);
return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
}
double LineCrossCircle(const Point &a, const Point &b, const Point &r,
double R, Point &p1, Point &p2)
{
Point fp = LineCross(r, Point(r.x + a.y - b.y, r.y + b.x - a.x), a, b);
double rtol = r.Dis(fp);
double rtos = fp.OnSeg(a, b) ? rtol : min(r.Dis(a), r.Dis(b));
double atob = a.Dis(b);
double fptoe = sqrt(R * R - rtol * rtol) / atob;
if(rtos > R - eps) return rtos;
p1 = fp + (a - b) * fptoe;
p2 = fp + (b - a) * fptoe;
return rtos;
}
double SectorArea(const Point &r, const Point &a, const Point &b, double R)
// 180 ,r->a->b
{
double A2 = Sqr(r - a), B2 = Sqr(r - b), C2 = Sqr(a - b);
return R * R * acos((A2 + B2 - C2) * 0.5 / sqrt(A2) / sqrt(B2)) * 0.5;
}
double TACIA(const Point &r, const Point &a, const Point &b, double R)
//TriangleAndCircleIntersectArea, ,r
{
double adis = r.Dis(a), bdis = r.Dis(b);
if(adis < R + eps && bdis < R + eps) return r.cross(a, b) * 0.5;
Point ta, tb;
if(r.InLine(a, b)) return 0.0;
double rtos = LineCrossCircle(a, b, r, R, ta, tb);
if(rtos > R - eps) return SectorArea(r, a, b, R);
if(adis < R + eps) return r.cross(a, tb) * 0.5 + SectorArea(r, tb, b, R);
if(bdis < R + eps) return r.cross(ta, b) * 0.5 + SectorArea(r, a, ta, R);
return r.cross(ta, tb) * 0.5 +
SectorArea(r, a, ta, R) + SectorArea(r, tb, b, R);
}
Point P[505], A, B;
int n;
double K;
double SPICA(Point r, double R) {
double res = 0;
for (int i = 0; i < n; i++) {
double temp = dcmp(r.cross(P[i], P[i + 1]));
if (temp < 0) res -= TACIA(r, P[i + 1], P[i], R);
else res += TACIA(r, P[i], P[i + 1], R);
}
return fabs(res);
}
int main() {
int cas = 1;
while (scanf("%d%lf", &n, &K) == 2) {
for (int i = 0; i < n; i++)
scanf("%lf%lf", &P[i].x, &P[i].y);
P[n] = P[0];
scanf("%lf%lf", &A.x, &A.y);
scanf("%lf%lf", &B.x, &B.y);
double D = (2.0 * K * K * A.x - 2.0 * B.x) / (1.0 - K * K);
double E = (2.0 * K * K * A.y - 2.0 * B.y) / (1.0 - K * K);
double F = (B.x * B.x + B.y * B.y - K * K * (A.x * A.x + A.y * A.y)) / (1.0 - K * K);
double res = SPICA(Point(-D * 0.5, -E * 0.5), sqrt(D * D + E * E - 4.0 * F) * 0.5);
printf("Case %d: %.10lf
", cas++, res);
}
return 0;
}