hdu 5130 2014 ACM/ICPC Regional Guangzhou 计算几何

由高中平面解析几何得：平面某一点P与两点A、B满足|PA|=k|PB|，则点P的轨迹是一个圆。
所以应求多边形与圆的公共面积，可将多边形分解为三角形来求。

/** Sep 9, 2015 3:23:33 PM
 * PrjName:hdu5130
 * @author Semprathlon
 */
import java.util.*;
import java.io.*;
public class Main {

    /**
     * @param args
     */
    static double sqr(double x){
        return x*x;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int cas=0;
        while(in.nextLine()!=null){
            int n=in.nextInt();
            double k=in.nextDouble();
            Polygon pl=new Polygon(n);
            for(int i=0;i<n;i++)
                pl.v[i]=new Point(in.nextInt(), in.nextInt());
            pl.v[n]=pl.v[0];
            Point A=new Point(in.nextDouble(),in.nextDouble());
            Point B=new Point(in.nextDouble(), in.nextDouble());
            Point O=new Point(-(B.x-k*k*A.x)/(k*k-1), -(B.y-k*k*A.y)/(k*k-1));
            double r=Math.sqrt(sqr((B.x-k*k*A.x)/(k*k-1))+sqr((B.y-k*k*A.y)/(k*k-1))-k*k*(sqr(A.x)+sqr(A.y))/(k*k-1)+(sqr(B.x)+sqr(B.y))/(k*k-1));
            Round R=new Round(r, O.x, O.y);
            double ans=0;
            for(int i=0;i<n;i++)
                ans+=Round.TriAngleCircleInsection(R, pl.v[i], pl.v[i+1]);
            out.println(String.format("Case %d: %.6f", ++cas,Math.abs(ans)));
            //out.println(r+" "+O.x+" "+O.y);
            //out.println(R.GetCirclePolyIntersectionArea(pl));
        }
        out.flush();
        out.close();
    }

}
class Point {
    double x, y;

    Point() {}
    Point(double _x, double _y) {}
    Point(Point p) {}
    Point add(Point r) {}
    Point sub(Point r) {}
    Point mul(double r) {}
    Point move(double dx, double dy) {}
    Point rotate(double a) {}
    Point rotate(double dx, double dy, double a) {}
    static Point mid(Point a, Point b) {}
    static double dist(Point a, Point b) {}
    public boolean equals(Point p) {}
    static void swap(Point a, Point b) {}
    static class Comp implements Comparator<Point> {}

    final static double eps = 1e-3;
    static int dcmp(double d) {
        if (Math.abs(d) < eps)
            return 0;
        return d > 0 ? 1 : -1;
    }

}
class Vector extends Point {
    Vector() {}
    Vector(double _x, double _y) {}
    Vector(Point a, Point b) {}
    Vector(Point p) {}
    static double angle(Vector a, Vector b) {}
    static double angle(Point a, Point b) {}
    static double angle(Point o, Point a, Point b) {}
    double dot(Vector r) {}
    double cross(Vector r) {}
    double length() {}
    Vector normal() {}
    static Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {}
    static Point GetLineIntersection(Point p, Point v, Point q, Point w) {}
    static Vector add(Vector a, Vector b) {}
    static double dot(Vector a, Vector b) {}
    static double cross(Vector a, Vector b) {}
    static double cross(Point a, Point b) {}
    static double cross(Point o, Point a, Point b) {}
    static double cross(Point a, Point b, Point c, Point d) {}
    static double length(Vector r) {}
}
class Line extends Vector {
    Point s, e;

    Line() {}
    Line(Point _s, Point _e) {}
    Line(double x1, double y1, double x2, double y2) {}
    Vector vector(){}
    static boolean isLineInter(Line l1, Line l2) {}
    static boolean isSegInter(Point s1, Point e1, Point s2, Point e2) {}
    static boolean isSegInter2(Point p1, Point p2, Point p3, Point p4){}
    static boolean isSegInter(Line l1, Line l2) {}
    static boolean isSegInter2(Line l1, Line l2) {}
}
class Polygon extends Vector {
    int num;
    Point[] v;
    Polygon() {}
    Polygon(int n) {}

    boolean IsConvexBag() {
        int direction = 0;// 1:右手正螺旋，逆时针 -1:左手正螺旋，顺时针
        for (int i = 0; i < num; i++) {
            int tmp = dcmp(cross(v[i], v[i + 1], v[i + 1], v[i + 2]));

            if (direction == 0) // 避免最初的点出现共线的情况
                direction = tmp;

            if (direction * tmp < 0) // 只要Vec是凸包，那么无论Vec的旋转方向如何，direction*temp都会>=0
                return false;
        }
        return true;
    }

}
class Round extends Vector {
    double r;
    Point o;
    final static double pi = Math.acos(-1.0);

    Round(double _r, double _x, double _y) {}
    static double Rad2Deg(double rad) {}
    static double Deg2Rad(double deg) {}
    double Area() {}

    static double CommonArea(Round A, Round B) {
        double area = 0.0;
        Round M = dcmp(A.r - B.r) > 0 ? A : B;
        Round N = dcmp(A.r - B.r) > 0 ? B : A;
        double D = dist(M.o, N.o);
        if (dcmp(M.r + N.r - D) > 0 && dcmp(M.r - N.r - D) < 0) {
            double cosM = (M.r * M.r + D * D - N.r * N.r) / (2.0 * M.r * D);
            double cosN = (N.r * N.r + D * D - M.r * M.r) / (2.0 * N.r * D);
            double alpha = 2.0 * Math.acos(cosM);
            double beta = 2.0 * Math.acos(cosN);

            double TM = 0.5 * M.r * M.r * Math.sin(alpha);
            double TN = 0.5 * N.r * N.r * Math.sin(beta);
            double FM = 0.5 * alpha / pi * M.Area();
            double FN = 0.5 * beta / pi * N.Area();
            area = FM + FN - TM - TN;
        } else if (dcmp(M.r - N.r - D) >= 0) {
            area = N.Area();
        }
        return area;
    }

    /* 判断圆与多边形的关系 */
    boolean IsFitPoly(Polygon pl) {
        for (int i = 0; i <= pl.num; i++) {
            int k = dcmp(Math.abs(cross(o, pl.v[i], o, pl.v[i + 1]) / dist(pl.v[i], pl.v[i + 1])) - r);
            if (k < 0)
                return false;
        }
        return true;
    }

    boolean IsInPoly(Polygon pl) {
        double CircleAngle = 0.0; // 环绕角
        for (int i = 1; i <= pl.num; i++) // 注意重复边不计算
            if (dcmp(cross(o, pl.v[i], o, pl.v[i + 1])) >= 0)
                CircleAngle += angle(o, pl.v[i], pl.v[i + 1]);
            else
                CircleAngle -= angle(o, pl.v[i], pl.v[i + 1]);

        if (dcmp(CircleAngle) == 0) // CircleAngle=0, Peg在多边形外部
            return false;
        else if (dcmp(CircleAngle - pi) == 0 || dcmp(CircleAngle + pi) == 0) // CircleAngle=180,
                                                                                // Peg在多边形边上(不包括顶点)
        {
            if (dcmp(r) == 0)
                return true;
        } else if (dcmp(CircleAngle - 2 * pi) == 0 || dcmp(CircleAngle + 2 * pi) == 0) // CircleAngle=360,
                                                                                        // Peg在多边形边内部
            return true;
        else // CircleAngle=(0,360)之间的任意角， Peg在多边形顶点上
        {
            if (dcmp(r) == 0)
                return true;
        }
        return false;
    }
    
    static double TriAngleCircleInsection(Round C, Point A, Point B)
    {
        Vector OA = new Vector(A.sub(C.o)), OB = new Vector(B.sub(C.o));
        Vector BA = new Vector(A.sub(B)), BC = new Vector(C.o.sub(B));
        Vector AB = new Vector(B.sub(A)), AC = new Vector(C.o.sub(A));
        double DOA = OA.length(), DOB = OB.length(),DAB = AB.length(), r = C.r;
        if(dcmp(cross(OA,OB)) == 0) return 0;
        if(dcmp(DOA-C.r) < 0 && dcmp(DOB-C.r) < 0) return cross(OA,OB)*0.5;
        else if(dcmp(DOB-r)<0 && dcmp(DOA-r) >= 0) {
            double x = (dot(BA,BC) + Math.sqrt(r*r*DAB*DAB-cross(BA,BC)*cross(BA,BC)))/DAB;
            double TS = cross(OA,OB)*0.5;
            return Math.asin(TS*(1-x/DAB)*2/r/DOA)*r*r*0.5+TS*x/DAB;
        }
        else if(dcmp(DOB-r) >=0 && dcmp(DOA-r) <0 ) {
            double y = (dot(AB,AC)+Math.sqrt(r*r*DAB*DAB-cross(AB,AC)*cross(AB,AC)))/DAB;
            double TS = cross(OA,OB)*0.5;
            return Math.asin(TS*(1-y/DAB)*2/r/DOB)*r*r*0.5+TS*y/DAB;
        }
        else if(dcmp(Math.abs(cross(OA,OB))-r*DAB)>=0 || dcmp(dot(AB,AC)) <= 0 || dcmp(dot(BA,BC)) <= 0) {
            if(dcmp(dot(OA,OB)) < 0) {
                if(dcmp(cross(OA,OB)) < 0) return (-Math.acos(-1.0)-Math.asin(cross(OA,OB)/DOA/DOB))*r*r*0.5;
                else                 return ( Math.acos(-1.0)-Math.asin(cross(OA,OB)/DOA/DOB))*r*r*0.5;
            }
            else                     return Math.asin(cross(OA,OB)/DOA/DOB)*r*r*0.5;
        }
        else {
            double x = (dot(BA,BC)+Math.sqrt(r*r*DAB*DAB-cross(BA,BC)*cross(BA,BC)))/DAB;
            double y = (dot(AB,AC)+Math.sqrt(r*r*DAB*DAB-cross(AB,AC)*cross(AB,AC)))/DAB;
            double TS = cross(OA,OB)*0.5;
            return (Math.asin(TS*(1-x/DAB)*2/r/DOA)+Math.asin(TS*(1-y/DAB)*2/r/DOB))*r*r*0.5 + TS*((x+y)/DAB-1);
        }
    }
}