Submission #201545

#	Time	Username	Problem	Language	Result	Execution time	Memory
201545		gs18115	Fences (JOI18_fences)	C++14	51 / 100	51 ms	1400 KiB

fences

#include<iostream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
typedef pair<double,double>pd;
typedef pair<pd,pd>ln;
const int inf=1e9+7;
const ll INF=1e18;
const double eps=1e-6;
const ln xa(pd(0,0),pd(INF,0));
pd operator-(pd x,pd y)
{
    return pd(x.fi-y.fi,x.se-y.se);
}
inline double ccw(pd x,pd y)
{
    return x.fi*y.se-x.se*y.fi;
}
inline double sq(double x)
{
    return x*x;
}
inline double dist(pd x,pd y)
{
    return sqrt(sq(x.fi-y.fi)+sq(x.se-y.se));
}
inline double dot(pd x,pd y)
{
    return x.fi*y.fi+x.se*y.se;
}
inline bool cross1(ln x,ln y)
{
    bool xc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<-eps;
    swap(x,y);
    bool yc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<-eps;
    return xc&&yc;
}
inline bool cross2(ln x,ln y)
{
    bool xc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<eps;
    swap(x,y);
    bool yc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<eps;
    return xc&&yc;
}
inline pd cut(ln x,double r)
{
    return pd(x.fi.fi*(1-r)+x.se.fi*r,x.fi.se*(1-r)+x.se.se*r);
}
inline pd perp(pd x,ln y)
{
    double rs=0;
    double re=1;
    while(re-rs>eps)
    {
        double r1=(rs*2+re)/3;
        double r2=(rs+re*2)/3;
        if(dist(x,cut(y,r1))<dist(x,cut(y,r2)))
            re=r2;
        else
            rs=r1;
    }
    return cut(y,rs);
}
double d[505][505];
inline void init(int n)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            d[i][j]=INF;
    for(int i=0;i<n;i++)
        d[i][i]=0;
    return;
}
inline void app(int i,int j,double y)
{
    d[i][j]=min(d[i][j],y);
    d[j][i]=min(d[j][i],y);
    return;
}
vector<ln>rs;
inline void app(int i,int j,int sz,pd x,pd y)
{
    for(ln&t:rs)
        if(cross1(t,ln(x,y)))
            return;
    double nd=dist(x,y);
    if(cross1(xa,ln(x,y)))
        app(i,j+sz,nd),app(i+sz,j,nd);
    else
        app(i,j,nd),app(i+sz,j+sz,nd);
    return;
}
inline void floyd(int n)
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    double s;
    cin>>n>>s;
    vector<ln>v;
    vector<pd>rp;
    rp.eb(s,s),rp.eb(-s,s),rp.eb(-s,-s),rp.eb(s,-s);
    rs.eb(rp[0],rp[2]);
    rs.eb(rp[1],rp[3]);
    for(pd&t:rp)
        v.eb(t,t);
    for(int i=0;i<n;i++)
    {
        pd x,y;
        cin>>x.fi>>x.se>>y.fi>>y.se;
        if(cross2(xa,ln(x,y)))
        {
            if(x.se<y.se)
                swap(x,y);
            if(x.se>eps)
                v.eb(x,cut(ln(x,y),x.se/(x.se-y.se))),v.back().se.se+=eps;
            if(y.se<-eps)
                v.eb(cut(ln(x,y),x.se/(x.se-y.se)),y),v.back().fi.se-=eps;
        }
        else
            v.eb(x,y);
    }
    n=v.size();
    init(n*2);
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            app(i,j,n,v[i].fi,v[j].fi);
            app(i,j,n,v[i].fi,v[j].se);
            app(i,j,n,v[i].se,v[j].fi);
            app(i,j,n,v[i].se,v[j].se);
            app(i,j,n,v[i].fi,perp(v[i].fi,v[j]));
            app(i,j,n,v[i].se,perp(v[i].se,v[j]));
            app(i,j,n,v[j].fi,perp(v[j].fi,v[i]));
            app(i,j,n,v[j].se,perp(v[j].se,v[i]));
        }
    }
    floyd(n*2);
    double m=INF;
    for(int i=0;i<n;i++)
        m=min(m,d[i][i+n]);
    cout<<fixed<<setprecision(12)<<m<<endl;
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 0 / 49