uva 11177(凸多邊形和圓的相交)

uva 11177(凸多邊形和圓的相交)

題意：按順時針或逆時針順序給出一個凸n邊形的n個點的坐標，然後讓一個圓心在(0,0)的圓和凸n邊形相交的面積大於等於R，問圓的最小半徑。
題解：這題簡直坑爹啊，各種細節錯誤。。修修改改了一天，最後看別人題解也還是不懂為什麼OnSegment函數要寫成那樣。。。明明不能判斷點是否在線段上 ╮(╯▽╰)╭
畫畫圖思路不難想到，把凸n邊形的每條邊都和圓判斷關系，如果是邊的兩點都在圓內，兩條邊對應一個三角形的面積，如果一個點在圓外一個在圓內(包括邊界)，那就是一個三角形加一個扇形，如果兩點都在圓外，分兩種情況，和圓有兩個交點的話是兩個扇形和一個三角形，如果和圓無交點是一個扇形。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1);

int dcmp(double x) {
    if (fabs(x) < eps)
        return 0;
    return x > 0 ? 1 : -1;
}
struct Point {
    double x, y;
    Point (double a = 0, double b = 0): x(a), y(b) {}
};
typedef Point Vector;

Vector operator + (const Vector& a, const Vector& b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (const Vector& a, const Vector& b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (const Vector& a, double& b) { return Vector(a.x * b, a.y * b); }
Vector operator / (const Vector& a, double& b) { return Vector(a.x / b, a.y / b); }
bool operator == (const Vector& a, const Vector& b) { return !dcmp(a.x - b.x) && !dcmp(a.y - b.y); }
bool operator < (const Vector& a, const Vector& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
double Dot(const Vector& a, const Vector& b) { return a.x * b.x + a.y * b.y; }
double Length(const Vector& a) { return sqrt(Dot(a, a)); }
double Cross(const Vector& a, const Vector& b) { return a.x * b.y - a.y * b.x; }
double Angle(const Vector& a, const Vector& b) { return acos(Dot(a, b) / Length(a) / Length(b)); }

struct Line {
    Point p;
    Vector v;
    double ang;
    Line() {}
    Line(Point a, Vector b): p(a), v(b) { ang = atan2(b.y, b.x); }
    bool operator < (const Line& L) const { return ang < L.ang; }
    Point point(double a) { return p + v * a; }
};
struct Circle {
    double r;
    Point c;
    Circle() {}
    Circle(Point a, double b): c(a), r(b) {}
    Point point(double a) { return Point(c.x + cos(a) * r, c.y + sin(a) * r); }
};

bool isPointInCircle(Point P, Circle C) {
    return dcmp(Length(C.c - P) - C.r) <= 0;
}

bool OnSegment(Point p, Point p1, Point p2) {
    return dcmp(Dot(p1 - p, p2 - p)) <= 0;//這裡很費解
}

void SegmentCircleIntersection(Point p1, Point p2, Circle C, Point* sol, int& num) {
    double t1, t2;
    double a = (p1 - C.c).x, b = (p2 - p1).x, c = (p1 - C.c).y, d = (p2 - p1).y;
    double e = b * b + d * d, f = 2 * (a * b + c * d), g = a * a + c * c - C.r * C.r;
    double delta = f * f - 4 * e * g;
    Point p;
    num = 0;
    if (dcmp(delta) < 0)
        return;
    else if (dcmp(delta) == 0) {
        t1 = t2 = (-f) / (2 * e);
        p = p1 + (p2 - p1) * t1;
        if (OnSegment(p, p1, p2))
            sol[num++] = p;
    }
    else {
        t1 = (-f - sqrt(delta)) / (2 * e);
        p = p1 + (p2 - p1) * t1;
        if (OnSegment(p, p1, p2))
            sol[num++] = p;
        t2 = (-f + sqrt(delta)) / (2 * e);
        p = p1 + (p2 - p1) * t2;
        if (OnSegment(p, p1, p2))
            sol[num++] = p;
    }
}

double FanArea(Circle C, Vector v1, Vector v2) {
    double rad = Angle(v1, v2);
    if (dcmp(rad - PI) == 0)
        rad = 0;
    return C.r * C.r * rad * 0.5;
}

double GetCommonArea(Point p1, Point p2, Point p3, Circle C) {
    int flag1 = isPointInCircle(p2, C);
    int flag2 = isPointInCircle(p3, C);
    int num;
    Point sol[5];
    if (flag1 + flag2 == 2)
        return fabs(Cross(p2 - p1, p3 - p1)) * 0.5;
    if (flag1 + flag2 == 1) {
        SegmentCircleIntersection(p2, p3, C, sol, num);
        if (flag1)
            return FanArea(C, p3 - p1, sol[0] - p1) + fabs(Cross(p2 - p1, sol[0] - p1)) * 0.5;
        return FanArea(C, p2 - p1, sol[0] - p1) + fabs(Cross(p3 - p1, sol[0] - p1)) * 0.5;
    }
    SegmentCircleIntersection(p2, p3, C, sol, num);//注意兩個端點對應不同交點，寫反就錯了
    if (num == 2)
        return FanArea(C, p2 - p1, sol[0] - p1) + fabs(Cross(sol[0] - p1, sol[1] - p1)) * 0.5 + FanArea(C, p3 - p1, sol[1] - p1);
    return FanArea(C, p2 - p1, p3 - p1);
}

const int N = 55;
Point P[N];
double R;
int n;

double CommonArea(Circle C) {
    double res = 0;
    for (int i = 0; i < n; i++)
        res += GetCommonArea(C.c, P[i], P[i + 1], C);
    return res;
}

int main() {
    int cas = 1;
    while (scanf(%d, &n) == 1 && n) {
        scanf(%lf, &R);
        for (int i = 0; i < n; i++)
            scanf(%lf%lf, &P[i].x, &P[i].y);
        P[n] = P[0];
        double l = 0, r = 1e9;
        while (dcmp(r - l) > 0) {
            double mid = (l + r) * 0.5;
            if (dcmp(CommonArea(Circle(Point(0, 0), mid)) - R) >= 0)
                r = mid;
            else
                l = mid;
        }
        printf(Case %d: %.2lf
, cas++, l);
    }
    return 0;
}