제출 #1313006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313006		Zero_OP	Fences (JOI18_fences)	C++20	100 / 100	78 ms	5160 KiB

fences

#include <bits/stdc++.h>

using namespace std;
bool BEGIN_ALLOC;

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)

tcT> bool minimize(T& a, const T& b){
    return (a > b ? a = b, 1 : 0);
}

tcT> bool maximize(T& a, const T& b){
    return (a < b ? a = b, 1 : 0);
}

tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

#define task "task"
void setIO(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
}

tcT> void _print(const T& x){ cerr << x; }
void _print(const string& s){ cerr << '"' << s << '"'; }
void _print(const char* s){ cerr << '"' << s << '"'; }
void _print(char c){ cerr << '\'' << c << '\''; }
void _print(bool b){ cerr << (b ? "True" : "False"); }

tcT, class U> void _print(const pair<U, T>& p){
    cerr << "("; _print(p.ff); cerr << ", "; _print(p.ss); cerr << ")";
}

tcT, class U, class V> void _print(const tuple<T, U, V>& t){
    cerr << "("; _print(get<0>(t)); cerr << ", "; _print(get<1>(t)); cerr << ", "; _print(get<2>(t)); cerr << ")";
}

template<class it> void _print(it a, it b, string sep = ", "){
    cerr << "{";
    bool first = false;
    for(it c = a; c != b; ++c){
        if(first) cerr << sep;
        _print(*c);
        first = true;
    }
    cerr << "}";
}

tcT> void _print(const vector<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const set<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const multiset<T>& v){ _print(begin(v), end(v)); }
tcT, class U> void _print(const map<T, U>& v){ _print(begin(v), end(v)); }

void mainPrint(){ cerr << '\n'; }
tcT> void mainPrint(const T& a){ _print(a); cerr << '\n';}
tcT, class... U> void mainPrint(const T& a, const U&... b){
    _print(a); 
    cerr << " | ";
    mainPrint(b...);
}

#define debug(...) (cerr << "[" << __FILE__ << "|#" << __LINE__ << "]" << " [" << #__VA_ARGS__ << "] = ", mainPrint(__VA_ARGS__))


const int MAX = 505;
const db eps = 1e-9;
using db = double;
struct P{
    db x, y;
    P() : x(0), y(0) {}
    P(db _x, db _y) : x(_x), y(_y) {}

    P operator + (P o){ return P(x + o.x, y + o.y); }
    P operator - (P o){ return P(x - o.x, y - o.y); }
    P operator * (db t){ return P(x * t, y * t); }

    db dot(P o) const { return x * o.x + y * o.y; }
    db cross(P o) const { return x * o.y - y * o.x; }
    db dot(P a, P b) const { return (a - *this).dot(b - *this); }
    db cross(P a, P b) const { return (a - *this).cross(b - *this); }

    db norm() const { return x * x + y * y; }
    db abs() const { return sqrt(norm()); }

    P perp() const { return P(y, -x); }

    bool operator == (P p) const { return std::abs(x - p.x) < eps && std::abs(y - p.y) < eps; }

    friend ostream& operator << (ostream& stream, const P& o){
        return stream << "(" << o.x << ", " << o.y << ")";
    }
};

struct Segment{
    P a, b;
    Segment() : a(), b() {}
    Segment(P a, P b) : a(a), b(b) {}

    bool onSegment(const P& p) const {
        return min(a.x, b.x) - eps <= p.x && p.x <= max(a.x, b.x) + eps && min(a.y, b.y) - eps <= p.y && p.y <= max(a.y, b.y) + eps && abs(a.cross(b, p)) < eps;
    }

    friend ostream& operator << (ostream& stream, Segment s){
        return stream << s.a << "--" << s.b;
    }
};

struct Edge{
    int u, v;
    double cost;
    Segment sg;

    Edge(int u, int v, double cost, Segment sg) : u(u), v(v), cost(cost), sg(sg) {}
};

struct Edge2{
    int u, v, t;
    double cost;
    Segment sg;

    Edge2(int u, int v, int t, double cost, Segment sg) : u(u), v(v), t(t), cost(cost), sg(sg) {}
};

int N, S;
db dist[MAX][MAX];
Segment segs[MAX], halfLine(P(0, 0), P(1e9 + 7, 1e9 + 9));
vector<Edge> edges;
vector<Edge2> edges2;

int turn(P a, P b, P c){
    double cr = a.cross(b, c);
    // cerr << fixed << setprecision(1);
    // debug(a, b, c);
    // debug(cr);
    return (cr > eps) - (cr < -eps);
}

bool segmentIntersect(const Segment& u, const Segment& v, bool acceptTouch){
    // debug(u, v);
    if(acceptTouch){
        if(u.onSegment(v.a) || u.onSegment(v.b)) return true;
        if(v.onSegment(u.a) || v.onSegment(u.b)) return true;
    }

    // cout << turn(u.a, u.b, v.a) << " " << turn(u.a, u.b, v.b) << '\n';
    // cout << turn(v.a, v.b, u.a) << " " << turn(v.a, v.b, u.b) << '\n';
    return turn(u.a, u.b, v.a) * turn(u.a, u.b, v.b) < 0 && turn(v.a, v.b, u.a) * turn(v.a, v.b, u.b) < 0;
}

P boxPoints[4];
bool touchRectangle(const Segment& s){
    F0R(i, 4){
        FOR(j, i + 1, 4){
            if(segmentIntersect(Segment(boxPoints[i], boxPoints[j]), s, false)) return true;
        }
    }
    return false;
}

int findParity(Segment s){
    return segmentIntersect(halfLine, s, false); 
}

P findProjection(Segment s, P c){
    if(s.a == s.b) return s.a;
    P ab = (s.b - s.a);
    P v = ab.perp();
    double t = (v.cross(c - s.a)) / v.cross(ab);
    return s.a + ab * t;
}

void findCosts(int u, int v, Segment p, Segment q){
    edges.pb(Edge(u << 1, v << 1, (p.a - q.a).abs(), Segment(p.a, q.a)));
    edges.pb(Edge(u << 1, v << 1 | 1, (p.a - q.b).abs(), Segment(p.a, q.b)));
    edges.pb(Edge(u << 1 | 1, v << 1, (p.b - q.a).abs(), Segment(p.b, q.a)));
    edges.pb(Edge(u << 1 | 1, v << 1 | 1, (p.b - q.b).abs(), Segment(p.b, q.b)));

    P best1 = findProjection(p, q.a);
    if(p.onSegment(best1)){
        Segment s(best1, q.a);
        int t = findParity(s);
        edges2.pb(Edge2(u << 1, v << 1, t ^ findParity(Segment(best1, p.a)), (best1 - q.a).abs(), s));
        edges2.pb(Edge2(u << 1 | 1, v << 1, t ^ findParity(Segment(best1, p.b)), (best1 - q.a).abs(), s));
    }

    P best2 = findProjection(p, q.b);
    if(p.onSegment(best2)){
        Segment s(best2, q.b);
        int t = findParity(s);
        edges2.pb(Edge2(u << 1, v << 1 | 1, t ^ findParity(Segment(best2, p.a)), (best2 - q.b).abs(), s));
        edges2.pb(Edge2(u << 1 | 1, v << 1 | 1, t ^ findParity(Segment(best2, p.b)), (best2 - q.b).abs(), s));
    }
 
    
    P best3 = findProjection(q, p.a);
    if(q.onSegment(best3)){
        Segment s(best3, p.a);
        int t = findParity(s);
        edges2.pb(Edge2(u << 1, v << 1, t ^ findParity(Segment(best3, q.a)), (best3 - p.a).abs(), s));
        edges2.pb(Edge2(u << 1, v << 1 | 1, t ^ findParity(Segment(best3, q.b)), (best3 - p.a).abs(), s));
    }

    P best4 = findProjection(q, p.b);
    if(q.onSegment(best4)){
        Segment s(best4, p.b);
        int t = findParity(s);
        edges2.pb(Edge2(u << 1 | 1, v << 1, t ^ findParity(Segment(best4, q.a)), (best4 - p.b).abs(), s));
        edges2.pb(Edge2(u << 1 | 1, v << 1 | 1, t ^ findParity(Segment(best4, q.b)), (best4 - p.b).abs(), s));
    }
}

void testcase(){
    cin >> N >> S;
    F0R(i, N){
        cin >> segs[i].a.x >>  segs[i].a.y >> segs[i].b.x >> segs[i].b.y;
    }

    int tmp = 0;
    for(auto x : {-S, S}){
        for(auto y : {-S, S}){
            P t(x, y);
            segs[N].a = segs[N].b = t;
            ++N;
            boxPoints[tmp++] = t;
        }
    }

    F0R(i, N * 4){
        F0R(j, N * 4){
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = 1e18;
        }
    }

    F0R(i, N){
        edges.pb(Edge(i << 1, i << 1 | 1, 0.0, segs[i]));
        FOR(j, i + 1, N){
            findCosts(i, j, segs[i], segs[j]);
        }
    }

    for(auto e : edges){
        if(touchRectangle(e.sg)) continue;
        int u = e.u, v = e.v;
        db w = e.cost;
        int t = findParity(e.sg);

        F0R(k, 2){
            minimize(dist[(u << 1) ^ k][(v << 1) ^ k ^ t], w);
            minimize(dist[(v << 1) ^ k ^ t][(u << 1) ^ k], w);
            minimize(dist[(v << 1) ^ k][(u << 1) ^ k ^ t], w);
            minimize(dist[(u << 1) ^ k ^ t][(v << 1) ^ k], w);
        }
    }

    for(auto e : edges2){
        if(touchRectangle(e.sg)) continue;
        int u = e.u, v = e.v;
        db w = e.cost;
        int t = e.t;

        F0R(k, 2){
            minimize(dist[(u << 1) ^ k][(v << 1) ^ k ^ t], w);
            minimize(dist[(v << 1) ^ k ^ t][(u << 1) ^ k], w);
            minimize(dist[(v << 1) ^ k][(u << 1) ^ k ^ t], w);
            minimize(dist[(u << 1) ^ k ^ t][(v << 1) ^ k], w);
        }
    }

    F0R(k, N * 4){
        F0R(i, N * 4){
            F0R(j, N * 4){
                minimize(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    db ans = 1e18;
    F0R(k, N * 2){
        minimize(ans, dist[k << 1][k << 1 | 1]);
    }
    cout << fixed << setprecision(10) << ans << '\n';
}

bool END_ALLOC;
int main(){
    auto startTime = chrono::steady_clock::now();
    setIO();

    int tests = 1;
    // cin >> tests;
    while(tests--){
        testcase();
    }

    auto endTime = chrono::steady_clock::now();
    cerr << fixed << setprecision(2) << "[Static memory: " << abs((&BEGIN_ALLOC) - (&END_ALLOC)) / (1024.0 * 1024.0) << "mb]\n";
    cerr << "[Time elapsed : " << chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count() << "ms]\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fences.cpp: In function 'void setIO()':
fences.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fences.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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