제출 #1268337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268337		minhpk	Roads (CEOI20_roads)	C++20	100 / 100	124 ms	17572 KiB

roads

#include <bits/stdc++.h>
using namespace std;

#define double long double
#define int long long

struct Line{
    pair<int,int> a,b;
    int id = 0;

    double get(int x) const{
        if(a.first == b.first) return a.second;
        return (double)(a.second*(b.first-x)+b.second*(x-a.first))/(double)(b.first-a.first);
    }

    bool operator<(const Line& other) const{
        return (*this).get(max(a.first,other.a.first)) < other.get(max(a.first,other.a.first));
    }
};

vector<tuple<int,int,int,int>> v;
Line a[1000005];
pair<int,int> pre[1000005];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("squares.in","r",stdin);
//    freopen("squares.out","w",stdout);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 > x2 || (x1 == x2 && y1 > y2)) swap(x1,x2), swap(y1,y2);

        v.push_back({x1,y1,i,1});
        v.push_back({x2,y2,i,2});
        a[i].a = {x1,y1}; a[i].b = {x2,y2}; a[i].id = i;
    }
    a[0].a = {-1e9,-1e9}; a[0].b = {1e9,-1e9}; a[0].id = 0;

    sort(v.begin(), v.end());
    set<Line> s;
    s.insert(a[get<2>(v[0])]);
    s.insert(a[0]);

    pre[0] = pre[get<2>(v[0])] = a[get<2>(v[0])].a;

    if(a[get<2>(v[0])].a.first == a[get<2>(v[0])].b.first) pre[0] = pre[get<2>(v[0])] = a[get<2>(v[0])].b;

    for(auto p : v){
        if(get<2>(p) == get<2>(v[0]) && get<3>(p) == 1) continue;
        int x = get<0>(p), y = get<1>(p), i = get<2>(p);

        if(get<3>(p) == 1){
            s.insert(a[i]);
            auto it = s.lower_bound(a[i]); it--;
            cout<< x << ' '  << y << ' ' << pre[it->id].first << ' ' << pre[it->id].second << '\n';
            pre[it->id] = a[i].a;

            if(a[i].a.first == a[i].b.first) pre[i] = a[i].b;
            else pre[i] = a[i].a;
        }else{
            auto it = s.lower_bound(a[i]); it--;

            pre[it->id] = a[i].b;
            s.erase(a[i]);
        }
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40