poj 3675 Telescope(三角断面多角形と円交面積を求める)

Telescope
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 2271
 
Accepted: 673
Description
Updog is watching a plane object with a telescope. The field of vision in the telescope can be described as a circle. The center is at the origin and the radius is R. The object can be seen as a simple polygon of N vertexes. Updog wants to know the area of the part of the object that can be seen in the telescope.
Input
The input will contain several test cases. For each case: The first line contains only one real number R.  The second line contains an integer N. The following N lines contain two real numbers xi and yi each, which describe the coordinates of a vertex. Two vertexes in adjacent lines are also adjacent on the polygon.  Constraints: 3 ≤ N ≤50, 0.1 ≤ R ≤1000, -1000 ≤ xi, yi ≤ 1000
Output
For each test case, output one real number on a separate line, which is the area of the part that can be seen. The result should be rounded to two decimal places.
Sample Input

10
3
0 20
10 0
-10 0

Sample Output

144.35

Source
POJ Founder Monthly Contest – 2008.07.27, Updog
题意:ひとつの円心を求めて原点の半径のrの円と1つの多角形の交面积で、多角形が退化して自ら交际しないことを保证します
题解:多角形を円心に基づいてn部分の三角形と円の交差に分割し、三角形と円の交差面积を状况によって计算します..
幾何学を説明する問題の山で、円についてのいろいろな計算をよく熟知することができます.のでも面倒くさい...間違いやすい...5時間近くやりました
三角形と円交の基本はこのブログで詳しくhttp://hi.baidu.com/billdu/item/703ad4e15d819db52f140b0b

#include
#include
#include
#define eps 1e-8
using namespace std;
struct point{
    double x,y;
    point(){}
    point(double x_,double y_):x(x_),y(y_){}
}p[58],tp[2],origin;
double r,area;
int n;
double MIN(double x,double y){ return xy?x:y; }
double cross(point p1,point p2,point p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
double dot(point p1,point p2)
{
    return p1.x*p2.x+p1.y*p2.y;
}
double dis(point p1,point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
struct point get_intersect()
{
    struct point temp=point(tp[0].x-tp[1].x,tp[0].y-tp[1].y);
    struct point vec=point(temp.y,-temp.x);
    struct point origin2=point(origin.x+vec.x,origin.y+vec.y);
    double a1=tp[0].y-tp[1].y;
    double b1=tp[1].x-tp[0].x;
    double c1=(tp[0].x*tp[1].y-tp[1].x*tp[0].y);
    double a2=origin.y-origin2.y;
    double b2=origin2.x-origin.x;
    double c2=(origin.x*origin2.y-origin2.x*origin.y);
    double tmd=a1*b2-a2*b1;
    return point((b1*c2-b2*c1)/tmd,(a2*c1-a1*c2)/tmd);
};
int on_line(point p0,point p1,point p2)
{
    if(p0.x>MAX(p1.x,p2.x)) return 0;
    if(p0.xMAX(p1.y,p2.y)) return 0;
    if(p0.y0)
    {
        for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
        p[n+1]=p[1];
        solve();
        printf("%.2lf
",fabs(area));
    }

    return 0;
}