제출 #1324147

#제출 시각아이디문제언어결과실행 시간메모리
1324147Zbyszek99Fences (JOI18_fences)C++20
100 / 100
292 ms6708 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const ld eps = 0.02137;

struct edge
{
    int v;
    ld dist;
    int is;
};

int n;
ld S;
pair<ld,ld> points[210];
vector<edge> graph[210];
ld dist[450][450];

bool is_inter_S(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3, ld x4, ld y4)
{
    if(y3 != y4)
    {
        swap(x1,y1);
        x1 *= -1;
        swap(x2,y2);
        x2 *= -1;
        swap(x3,y3);
        x3 *= -1;
        swap(x4,y4);
        x4 *= -1;
    }
    if(x1 == x2) return x1 > min(x3,x4) && x1 < max(x3,x4) && y3 > min(y1,y2) && y3 < max(y1,y2);
    if(y1 == y2) return 0;
    ld b1 = (y1*x2-y2*x1)/(x2-x1);
    ld a1 = 0;
    if(x1 != 0) a1 = (y1-b1)/x1;
    else a1 = (y2-b1)/x2;
    ld b2 = y3;
    ld a2 = 0;
    ld x = (b2-b1)/(a1-a2);
    return min(x1,x2) < x && x < max(x1,x2) && min(x3,x4) < x && x < max(x3,x4);
}

bool is_valid(ld x1, ld y1, ld x2, ld y2)
{
    return !is_inter_S(x1,y1,x2,y2,-S,S-eps,S,S-eps)&&!is_inter_S(x1,y1,x2,y2,-S,-S+eps,S,-S+eps)&&!is_inter_S(x1,y1,x2,y2,S-eps,-S,S-eps,S)&&!is_inter_S(x1,y1,x2,y2,-S+eps,-S,-S+eps,S);
}

pair<ld,ld> opt_point(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3)
{
    ld A,B,C;
    if(x1 != x2)
    {
        ld b1 = (y1*x2-y2*x1)/(x2-x1);
        ld a1 = 0;
        if(x1 != 0) a1 = (y1-b1)/x1;
        else a1 = (y2-b1)/x2;
        A = a1;
        B = -1;
        C = b1;
    }
    else
    {
        A = 1;
        B = 0;
        C = -x1;
    }
    ld opt_x = x3-A*((A*x3+B*y3+C)/(A*A+B*B));
    ld opt_y = y3-B*((A*x3+B*y3+C)/(A*A+B*B));
    if(opt_x < min(x1,x2) || opt_x > max(x1,x2) || opt_y < min(y1,y2) || opt_y > max(y1,y2)) return {x1,y1};
    return {opt_x,opt_y};
}

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> n >> S;
    rep(i,n)
    {
        cin >> points[i*2].ff >> points[i*2].ss >> points[i*2+1].ff >> points[i*2+1].ss;
        bool is = is_inter_S(points[i*2].ff,points[i*2].ss,points[i*2+1].ff,points[i*2+1].ss,0,eps,1e6,eps);
        graph[i*2].pb({i*2+1,0,is});
        graph[i*2+1].pb({i*2,0,is});
    }
    points[n*2] = {S,S};
    points[n*2+1] = {S,-S};
    points[n*2+2] = {-S,-S};
    points[n*2+3] = {-S,S};
    vector<pair<ld,ld>> pot;
    rep2(i,n*2,n*2+3)
    {
        rep2(j,n*2,n*2+3)
        {
            if(i == j || abs(i-j) == 2) continue;
            int is = is_inter_S(points[i].ff,points[i].ss,points[j].ff,points[j].ss,0,eps,1e6,eps);
            graph[i].pb({j,2*S,is});
            graph[j].pb({i,2*S,is});
        }
    }
    rep2(i,0,n*2+3)
    {
        rep(s,n)
        {
            pot = {{points[s*2].ff,points[s*2].ss},{points[s*2+1].ff,points[s*2+1].ss},opt_point(points[s*2].ff,points[s*2].ss,points[s*2+1].ff,points[s*2+1].ss,points[i].ff,points[i].ss)};
            pair<ld,int> min_d = {1e18,-1};
            int ind = 0;
            forall(it,pot)
            {
                if(is_valid(points[i].ff,points[i].ss,it.ff,it.ss)) min_d = min(min_d,{sqrtl((points[i].ff-it.ff)*(points[i].ff-it.ff)+(points[i].ss-it.ss)*(points[i].ss-it.ss)),ind});
                ind++;
            }
            if(min_d.ff != 1e18) 
            {
                int is = is_inter_S(points[i].ff,points[i].ss,pot[min_d.ss].ff,pot[min_d.ss].ss,0,eps,1e6,eps);
                int is2 = is_inter_S(points[s*2].ff,points[s*2].ss,pot[min_d.ss].ff,pot[min_d.ss].ss,0,eps,1e6,eps);
                graph[i].pb({s*2,min_d.ff,(is^is2)});
                graph[s*2].pb({i,min_d.ff,(is^is2)});
            }
        }
    }
    int add = n*2+4;
    rep(i,450) rep(j,450) dist[i][j] = 1e18;
    rep2(i,0,n*2+3)
    {
        forall(it,graph[i])
        {
            if(it.is == 0)
            {
                dist[i][it.v] = min(dist[i][it.v],it.dist);
                dist[i+add][it.v+add] = min(dist[i+add][it.v+add],it.dist);
            }
            else
            {
                dist[i][it.v+add] = min(dist[i][it.v+add],it.dist);
                dist[i+add][it.v] = min(dist[i+add][it.v],it.dist);    
            }
        }
    }
    rep2(k,0,n*4+7)
    {
        rep2(i,0,n*4+7)
        {
            rep2(j,0,n*4+7)
            {
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    ld ans = 1e18;
    rep2(i,0,n*2+3) ans = min(ans,dist[i][i+add]);
    cout << fixed << setprecision(8) << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...