uva 11978 Fukushima Nuclear Blast (二分+多边形与圆交)

二分+多边形与圆交就可以了

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;

const double PI = acos(-1.0);
const double EPS = 1e-8;

inline int sgn(double x) {
    return (x > EPS) - (x < -EPS);
}

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y): x(x), y(y) {}
    void read() {
        scanf("%lf%lf", &x, &y);
    }
    double angle() {
        return atan2(y, x);
    }
    Point operator + (const Point &rhs) const {
        return Point(x + rhs.x, y + rhs.y);
    }
    Point operator - (const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
    Point operator * (double t) const {
        return Point(x * t, y * t);
    }
    Point operator / (double t) const {
        return Point(x / t, y / t);
    }
    double operator *(const Point &b)const
    {
        return x*b.x + y*b.y;
    }
    double length() const {
        return sqrt(x * x + y * y);
    }
    Point unit() const {            //单位向量
        double l = length();
        return Point(x / l, y / l);
    }
};
double cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}
double sqr(double x) {
    return x * x;
}
double dist(const Point &p1, const Point &p2) {
    return (p1 - p2).length();
}
double sdist(Point a,Point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
//向量 op 逆时针旋转 angle
Point rotate(const Point &p, double angle, const Point &o = Point(0, 0)) {
    Point t = p - o;
    double x = t.x * cos(angle) - t.y * sin(angle);
    double y = t.y * cos(angle) + t.x * sin(angle);
    return Point(x, y) + o;
}
Point line_inter(Point A,Point B,Point C,Point D){ //直线相交交点
        Point ans;
        double a1=A.y-B.y;
        double b1=B.x-A.x;
        double c1=A.x*B.y-B.x*A.y;

        double a2=C.y-D.y;
        double b2=D.x-C.x;
        double c2=C.x*D.y-D.x*C.y;

        ans.x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
        ans.y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
        return ans;
}
Point p_to_seg(Point p,Point a,Point b){        //点到线段的最近点
    Point tmp=p;
    tmp.x+=a.y-b.y;
    tmp.y+=b.x-a.x;
    if(cross(a-p,tmp-p)*cross(b-p,tmp-p)>0) return dist(p,a)<dist(p,b)?a:b;
    return line_inter(p,tmp,a,b);
}
void line_circle(Point c,double r,Point a,Point b,Point &p1,Point &p2){
    Point tmp=c;
    double t;
    tmp.x+=(a.y-b.y);//求垂直于ab的直线
    tmp.y+=(b.x-a.x);
    tmp=line_inter(tmp,c,a,b);
    t=sqrt(sqr(r)-sqr( dist(c,tmp)))/dist(a,b); //比例
    p1.x=tmp.x+(b.x-a.x)*t;
    p1.y=tmp.y+(b.y-a.y)*t;
    p2.x=tmp.x-(b.x-a.x)*t;
    p2.y=tmp.y-(b.y-a.y)*t;
}
struct Region {
    double st, ed;
    Region() {}
    Region(double st, double ed): st(st), ed(ed) {}
    bool operator < (const Region &rhs) const {
        if(sgn(st - rhs.st)) return st < rhs.st;
        return ed < rhs.ed;
    }
};
struct Circle {
    Point c;
    double r;
    vector<Region> reg;
    Circle() {}
    Circle(Point c, double r): c(c), r(r) {}
    void read() {
        c.read();
        scanf("%lf", &r);
    }
    void add(const Region &r) {
        reg.push_back(r);
    }
    bool contain(const Circle &cir) const {
        return sgn(dist(cir.c, c) + cir.r - r) <= 0;
    }
    bool intersect(const Circle &cir) const {
        return sgn(dist(cir.c, c) - cir.r - r) < 0;
    }
};
void intersection(const Circle &cir1, const Circle &cir2, Point &p1, Point &p2) {   //两圆相交 交点
    double l = dist(cir1.c, cir2.c);                            //两圆心的距离
    double d = (sqr(l) - sqr(cir2.r) + sqr(cir1.r)) / (2 * l);  //cir1圆心到交点直线的距离
    double d2 = sqrt(sqr(cir1.r) - sqr(d));                     //交点到 两圆心所在直线的距离
    Point mid = cir1.c + (cir2.c - cir1.c).unit() * d;
    Point v = rotate(cir2.c - cir1.c, PI / 2).unit() * d2;
    p1 = mid + v, p2 = mid - v;
}
Point calc(const Circle &cir, double angle) {
    Point p = Point(cir.c.x + cir.r, cir.c.y);
    return rotate(p, angle, cir.c);
}
const int MAXN = 1010;
Circle cir[MAXN],cir2[MAXN];
bool del[MAXN];
int n;
double get_area(Circle* cir,int n) {            //多个圆的相交面积
    double ans = 0;
    memset(del,0,sizeof(del));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) if(!del[j]) {                //删除被包含的圆
            if(i == j) continue;
            if(cir[j].contain(cir[i])) {
                del[i] = true;
                break;
            }
        }
    }
    for(int i = 0; i < n; ++i) if(!del[i]) {
        Circle &mc = cir[i];
        Point p1, p2;
        bool flag = false;
        for(int j = 0; j < n; ++j) if(!del[j]) {
            if(i == j) continue;
            if(!mc.intersect(cir[j])) continue;
            flag = true;
            intersection(mc, cir[j], p1, p2);                   //求出两圆的交点
            double rs = (p2 - mc.c).angle(), rt = (p1 - mc.c).angle();
            if(sgn(rs) < 0) rs += 2 * PI;
            if(sgn(rt) < 0) rt += 2 * PI;
            if(sgn(rs - rt) > 0) mc.add(Region(rs, PI * 2)), mc.add(Region(0, rt)); //添加相交区域
            else mc.add(Region(rs, rt));
        }
        if(!flag) {
            ans += PI * sqr(mc.r);
            continue;
        }
        sort(mc.reg.begin(), mc.reg.end());                 //对相交区域进行排序
        int cnt = 1;
        for(int j = 1; j < int(mc.reg.size()); ++j) {
            if(sgn(mc.reg[cnt - 1].ed - mc.reg[j].st) >= 0) {   //如果有区域可以合并，则合并
                mc.reg[cnt - 1].ed = max(mc.reg[cnt - 1].ed, mc.reg[j].ed);
            } else mc.reg[cnt++] = mc.reg[j];
        }
        mc.add(Region());
        mc.reg[cnt] = mc.reg[0];
        for(int j = 0; j < cnt; ++j) {
            p1 = calc(mc, mc.reg[j].ed);
            p2 = calc(mc, mc.reg[j + 1].st);
            ans += cross(p1, p2) / 2;                           //
            double angle = mc.reg[j + 1].st - mc.reg[j].ed;
            if(sgn(angle) < 0) angle += 2 * PI;
            ans += 0.5 * sqr(mc.r) * (angle - sin(angle));      //弧所对应的的面积
        }
    }
    return ans;
}
double two_cir(Circle t1,Circle t2){            //两个圆的相交面积
    if(t1.contain(t2)||t2.contain(t1))    return PI * sqr(min(t2.r,t1.r));
    if(!t1.intersect(t2)) return 0;
    double ans=0,len=dist(t1.c,t2.c);
    double x=(sqr(t1.r)+sqr(len)-sqr(t2.r))/(2*len);
    double angle1=acos(x/t1.r),angle2=acos((len-x)/t2.r);
    ans=sqr(t1.r)*angle1+sqr(t2.r)*angle2-len*t1.r*sin(angle1);    // 两个扇形 减去一个四边形面积
    return ans;
}
double triangle_circle(Point a,Point b,Point o,double r){
    double sign=1.0;
    double ans=0;
    Point p1,p2;
    a=a-o;b=b-o;
    o=Point(0,0);
    if(sgn(cross(a,b))==0) return 0.0;
    if(sdist(a,o)>sdist(b,o)){
        swap(a,b);
        sign=-1.0;
    }
    if(sdist(a,o)<r*r+EPS){  //a 在内， b 在外
        if(sdist(b,o)<r*r+EPS) return cross(a,b)/2.0*sign;
        line_circle(o,r,a,b,p1,p2);
        if(dist(p1,b)>dist(p2,b)) swap(p1,p2);
        double ans1=fabs(cross(a,p1));
        double ans2=acos(p1*b/p1.length()/b.length())*r*r;
        ans=(ans1+ans2)/2.0;
        if(cross(a,b)<EPS&&sign>0.0||cross(a,b)>EPS&&sign<0.0) return -ans;
        return ans;
    }
    Point tmp=p_to_seg(o,a,b);
    if(sdist(o,tmp)>r*r-EPS){    //a,b所在直线与圆没有交点
        double angle=a*b/a.length()/b.length();
        if(angle>1.0) angle=1;
        if(angle<-1.0) angle=-1.0;
        ans=acos(a*b/a.length()/b.length())*r*r/2.0;
        if(cross(a,b)<EPS&&sign>0.0||cross(a,b)>EPS&&sign<0.0) return -ans;
        return ans;
    }
    line_circle(o,r,a,b,p1,p2);
    double cm=r/(dist(a,o)-r);
    Point m=Point((o.x+cm*a.x)/(1+cm),(o.y+cm*a.y)/(1+cm) );
    double cn=r/(dist(o,b)-r);
    Point n=Point( (o.x+cn*b.x)/(1+cn) , (o.y+cn*b.y)/(1+cn) );
    double angle= m*n/m.length()/n.length();
    if(angle>1.0) angle=1;
    if(angle<-1.0) angle=-1.0;
    double ans1 = acos(m*n/m.length()/n.length())*r*r;
    angle=p1*p2/p1.length()/p2.length() ;
    if(angle>1.0) angle=1;
    if(angle<-1.0) angle=-1.0;
    double ans2 = acos(p1*p2/p1.length()/p2.length() )*r*r-fabs(cross(p1,p2));
    ans=(ans1-ans2)/2.0;
    if(cross(a,b)<EPS&&sign>0.0||cross(a,b)>EPS&&sign<0.0) return -ans;
    return ans;
}
Point pt[5100];
int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif // ONLINE_JUDGE
    Point a,b,c;
    double x1,y1,h,x2,y2,r,p;
    int t,cas=0;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=0;i<n;i++) pt[i].read();
        c.read();
        cin>>p;
        pt[n]=pt[0];
        double aLL=0,ans;
        for(int i=0;i<n;i++) aLL+=cross(pt[i],pt[i+1])/2.0;
        double l=0,r=1000000,mid;
        while(r-l>1e-3){
            mid=(l+r)/2;
            double sum=0;
            for(int i=0;i<n;i++) sum+=triangle_circle(pt[i],pt[i+1],c,mid);
            sum=fabs(sum);
            if(sum>=aLL*p/100) {
                ans=mid;
                r=mid;
            }
            else l=mid;
        }
        printf("Case %d: %.0f
",++cas,ans);
    }
}