Submission #44535290

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1.0)
#define pb push_back
#define double long double
const double eps = 1e-9;
int sgn(double x){
    if(x<eps&&x>-eps)return 0;
    if(x<0)return -1;
    return 1;
}
double cmp(double a,double b){return sgn(a-b);}
double sqr(double x){return x*x;}
double inmid(double x,double l,double r){return sgn(x-l)>=0&&sgn(r-x)>=0;}

struct Point{
    double x,y;
    Point(){}
    Point(double xx,double yy){x=xx;y=yy;}
    bool operator ==(const Point &p)const{return sgn(x-p.x)==0&&sgn(y-p.y)==0;}
    bool operator !=(const Point &p)const{return sgn(x-p.x)!=0||sgn(y-p.y)!=0;}
    bool operator < (const Point &p)const{
        return sgn(x-p.x)<0||(sgn(x-p.x)==0&&sgn(y-p.y)<0);
    }
    Point operator + (const Point &p)const{
        return {x+p.x,y+p.y};
    }
    Point operator - (const Point &p)const{
        return {x-p.x,y-p.y};
    }
    Point operator * (double k)const{
        return {x*k,y*k};
    }
    Point operator / (const double &k)const{
//assert(k!=0);
        return {x/k,y/k};
    }
    double dot(Point p) const{return p.x*x+p.y*y;}
    double cross(Point p) const {return x * p.y - y * p.x;}
    double dis(Point p) const {return sqrt(sqr(x - p.x) + sqr(y - p.y));}
    double abs() const{return sqrt(sqr(x)+sqr(y));}
    double abs2() const{return sqr(x)+sqr(y);}
    Point rot(Point p,double a){
//逆时针旋转
        Point v = (*this) - p;
        double c = cos(a), s = sin(a);
        return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
    }
    Point rotLeft() const{return Point(-y,x);}
    Point rotRight() const{return Point(y,-x);}
    double getW() const{return atan2(y,x);}
    Point unit()const{
        if(sgn(abs())==0)return (*this);
        else return {x/abs(),y/abs()};
    }
    Point trunc(double r)const{Point tmp=unit();return tmp*r;}
    double rad(Point a,Point b)const{
        Point k1=a-(*this),k2=b-(*this);
        return atan2(k1.cross(k2), k1.dot(k2));
    }
};
double cross(Point p1,Point p2,Point p3){
    return (p2-p1).cross(p3-p1);
}
double dot(Point p1,Point p2,Point p3){
    return (p2-p1).dot(p3-p1);
}
struct Line{
    Point s,e;//有向直线
    double ang;
    Line(){}
    Line(Point ss,Point ee){s=ss;e=ee;}
    bool operator ==(const Line &v)const{return s==v.s&&e==v.e;}
    void calcAng(){ang= atan2(dir().y,dir().x);}
    Point dir(){return e-s;}
    int checkLP(Point p){
/* s e p make a counterclockwise 1
* s e p make a clockwise 2
* p is on a line p s e 3
* p is on a line s e p 4
* p is on a seg s e 5
* error 6 */
        int tmp = sgn(cross(s,p,e));
        if(tmp<0)return 1;
        if(tmp>0)return 2;
        int dt=sgn(dot(p,s,e));
        if(dt<=0)return 5;
        if(sgn(dot(s,p,e))>0)return 4;
        if(sgn(dot(s,p,e))<0)return 3;
        assert(0);
    }
    int checkLL(Line v){
// 3 coincide 2 parallel 1 orthogonal 0 others
        int tmp = sgn((e-s).cross(v.e-v.s));
        if(tmp==0){
            if(v.checkLP(e)>2)return 3;
            return 2;
        }
        if(sgn((e-s).dot(v.e-v.s))==0)return 1;
        return 0;
    }
    int checkSS(Line v){
// 2 not strict 1 strict 0 not ins
        if(checkLP(v.s)==5|| checkLP(v.e)==5)return 2;
        if(v.checkLP(s)==5||v.checkLP(e)==5)return 2;
        int tmp=sgn(cross(s,e,v.s)* cross(s,e,v.e));
        int tmp2=sgn(cross(v.s,v.e,s)* cross(v.s,v.e,e));
        if(tmp<0&&tmp2<0)return 1;
        return 0;
    }
    int checkLS(Line v){//untested 2严格1不严格
        int d1 = sgn((e-s).cross(v.s-s));
        int d2 = sgn((e-s).cross(v.e-s));
        if((d1^d2)==-2) return 2;
        return (d1==0||d2==0);
    }
    Point getLL(Line v){
        double tmp=(s-v.s).cross(v.e-v.s),tmp2=(v.e-v.s).cross(e-v.s);
        return (s*tmp2+e*tmp)/(tmp+tmp2);
    }
    double len(){return (e-s).abs();}
    Point proj(Point p){
        return s+(e-s).trunc(dot(s,p,e)/len());
    }
    Point ref(Point p){
        Point tmp= proj(p);
        return tmp+tmp-p;
    }
    double disLP(Point p){return p.dis(proj(p));}
    double disSP(Point p){
        if(checkLP(proj(p))!=5)return min(p.dis(s),p.dis(e));
        return disLP(p);
    }
    Line trans(Point v,double d){
        Point tmp=v.trunc(d);
        return {s+tmp,e+tmp};
    }
    Line transLeft(double d){return trans((e-s).rotLeft(),d);}
    Line transRight(double d){return trans((e-s).rotRight(),d);}

};
bool onSeg(Point p,Point a,Point b){return Line(a,b).checkLP(p)==5;}
struct Circle {
    Point p;
    double r;

    Circle() {}

    Circle(Point pp, double rr) {
        p = pp;
        r = rr;
    }

    bool operator==(const Circle &c) const {
        return (p == c.p) && (sgn(r - c.r) == 0);
    }

    Point point(double a) { return p + Point(r * cos(a), r * sin(a)); }


    int include(Point q) {
        if (sgn(p.dis(q) - r) == 0)return 1;
        if (sgn(p.dis(q) - r)
            < 0)
            return 2;
        return 0;
    }

    int checkCC(Circle c) {
//0 内含 1 内切 2 相交 3 外切 4 相离
        double d = c.p.dis(p);
        if (sgn(d - r - c.r) > 0)return 4;
        if (sgn(d - r - c.r) == 0)return 3;
        if (sgn(d - fabs(r - c.r)) == 0)return 1;
        if (sgn(d - fabs(r - c.r)) < 0)return 0;
        return 2;
    }

    int checkCL(Line l) {
//2 相交 1相切 0 相离
        if (sgn(l.disLP(p) - r) == 0)return 1;
        if (sgn(l.disLP(p) - r) < 0)return 2;
        return 0;
    }
    vector<Point> getCC(Circle c){//沿当前逆时针给出,相切给出两个
        if(checkCC(c)==0|| checkCC(c)==4)return {};
        double b=p.dis(c.p),cosA=(r*r+b*b-c.r*c.r)/(2*r*b);
        double tmp=r*cosA,h=sqrt(r*r-tmp*tmp);
        Point v=(c.p-p).trunc(tmp).rotLeft().trunc(h);
        Point ini=p+(c.p-p).trunc(tmp);
        return {ini-v,ini+v};
    }
    vector<Point> getCL(Line v) {
//相切给出两个
        if (checkCL(v) == 0)return {};
        vector<Point> tmp;
        double d = v.disLP(p);
        double x = sqrt(r * r - d * d);
        if (sgn(d - r) == 0) {
            tmp.pb(v.proj(p));
            tmp.pb(v.proj(p));
        } else {
            tmp.pb(v.proj(p) - (v.e - v.s).trunc(x));
            tmp.pb(v.proj(p) + (v.e - v.s).trunc(x));
//和v方向一致
        }
        return tmp;
    }
};
vector<Line> ls;
int ja(Point p,double r){
    for(auto i:ls){
        if(sgn(i.disSP(p)-r)>0)return 0;
    }
    return 1;
}
int check(double r){
    int n=ls.size();
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            vector<Line> tmpi={ls[i].transLeft(r),ls[i].transRight(r)},
            tmpj={ls[j].transLeft(r),ls[j].transRight(r)};
            vector<Circle> csi = {Circle(ls[i].s,r),Circle(ls[i].e,r)};
            vector<Circle> csj = {Circle(ls[j].s,r),Circle(ls[j].e,r)};
            for(auto l1:tmpi){
                for(auto l2:tmpi){
                    if(l1.checkLL(l2)>=2)continue;
                    auto p=l1.getLL(l2);
                    if(ja(p,r))return 1;
                }
            }
            for(auto c1:csi){
                for(auto l2:tmpj){
                    auto tmp=c1.getCL(l2);
                    for(auto p:tmp){
                        if(ja(p,r))return 1;
                    }
                }
            }
            for(auto c2:csj){
                for(auto l1:tmpi){
                    auto tmp=c2.getCL(l1);
                    for(auto p:tmp){
                        if(ja(p,r))return 1;
                    }
                }
            }
            for(auto c2:csj){
                for(auto c1:csi){
                    auto tmp=c2.getCC(c1);
                    for(auto p:tmp){
                        if(ja(p,r))return 1;
                    }
                }
            }
        }
    }
    return 0;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout.precision(10);cout<<fixed;
    int t=1;
    for(int ii=1;ii<=t;ii++){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            Point l,r;
            cin>>l.x>>l.y>>r.x>>r.y;
            ls.push_back({l,r});
        }
        double l = 0,r=5000;
        for(int i=1;i<=30;i++){
            double mid=(l+r)/2.0L;
            if(check(mid))r= mid;
            else l=mid;
        }
        cout<<r<<"\n";
    }

}

Submission Info

Judge Result