제출 #1245900

#제출 시각아이디문제언어결과실행 시간메모리
1245900ericl23302Roads (CEOI20_roads)C++20
15 / 100
10 ms1608 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<pair<ll, ll>, pair<ll, ll>> line;

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<line> lines(n);
    for (auto &i : lines) {
        cin >> i.first.first >> i.first.second >> i.second.first >> i.second.second;
        if (i.second.first < i.first.first || (i.second.first == i.first.first && i.second.second < i.first.second)) swap(i.first, i.second);
    }

    ll changeInX = lines[0].second.first - lines[0].first.first, changeInY = lines[0].second.second - lines[0].first.second;

    sort(lines.begin(), lines.end(), [&](const line a, const line b) {
        if (changeInX == 0) {
            if (a.first.first == b.first.first) return a.first.second < b.first.second;
            return a.first.first < b.first.first;
        } else {
            double aYint = (double)(changeInY / changeInX) * (-a.first.first) + a.first.second;
            double bYint = (double)(changeInY / changeInX) * (-b.first.first) + b.first.second;
            if (abs(aYint - bYint) < 1e-9) {
                if (a.first.first == b.first.first) return a.first.second < b.first.second;
                return a.first.first < b.first.first;
            }
            return (bool)((aYint > bYint) ^ (changeInY < 0));
        }
    });

    for (int i = 0; i < n - 1; ++i) cout << lines[i].second.first << ' ' << lines[i].second.second << ' ' << lines[i + 1].first.first << ' ' << lines[i + 1].first.second << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...