Submission #379487

#TimeUsernameProblemLanguageResultExecution timeMemory
379487ACmachineRoads (CEOI20_roads)C++17
15 / 100
20 ms2284 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in) #define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in) #define REP(i,b) FOR(i,0,b,1) #define REPD(i,b) FORD(i,b,0,1) #define pb push_back #define mp make_pair #define ff first #define ss second #define all(x) begin(x), end(x) #define MANY_TESTS int tcase; cin >> tcase; while(tcase--) const double EPS = 1e-9; const int MOD = 1e9+7; const ll INFF = 1e18; const int INF = 1e9; const ld PI = acos((ld)-1); const vi dy = {1, 0, -1, 0, -1, 1, 1, -1}; const vi dx = {0, 1, 0, -1, -1, 1, -1, 1}; void DBG(){cout << "]" << endl;} template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); } #define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__); #define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl; template<class T, unsigned int U> ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;} template <class T, class U> ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;} template <class T> ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template <class T, class U> ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template<class T> ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;} template<class T> istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; } struct Frac{ long long n, d; Frac(long long n, long long d){ this->n = n; this->d = d; long long g = __gcd(n, d); this->n/=g; this->d/=g; if(this->d < 0){ this->n*=-1; this->d*=-1; }; } Frac(long long n){ this->n = n; d = 1; } Frac(){n = 0; d = 1;} Frac operator-(){return Frac(-n, d);} Frac operator+=(const Frac& other){return Frac(n*other.d + other.n*d, d*other.d);} Frac operator-=(const Frac& other){return Frac(n*other.d - other.n*d, d*other.d);} Frac operator*=(const Frac& other){return Frac(n*other.n, d*other.d);} Frac operator/=(const Frac& other){return Frac(n*other.d, d*other.n);} friend Frac operator+(Frac a, const Frac& b){ return a+=b; } friend Frac operator-(Frac a, const Frac& b){ return a-=b; } friend Frac operator*(Frac a, const Frac& b){ return a*=b; } friend Frac operator/(Frac a, const Frac& b){ return a/=b; } bool operator==(const Frac& other){ return n==other.n && d==other.d; } //bool operator<(const Frac& other){ return n*other.d < other.n*d; } bool operator!=(const Frac& other){ return !((*this)==other);} friend bool operator<(Frac a, Frac b){ return a.n * b.d < b.n * a.d; } friend string ts(const Frac& a){ return to_string(a.n) + "/" + to_string(a.d); } friend ostream& operator<<(ostream& out, Frac &a) { return out << ts(a); } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector<pair<int, pair<int, int>>> lines(n); bool vertical = false; vector<pair<Frac, array<int, 4>>> lines2(n); REP(i, n){ int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if(x1 == x2){ vertical = true; } if(vertical){ if(y1 > y2) swap(y1, y2); lines[i].ff = x1; lines[i].ss = make_pair(y1, y2); } else{ Frac slope = Frac(y1 - y2, x1 - x2); Frac c = Frac(y1) - (slope * Frac(x1)); lines2[i].ff = c; if(x1 > x2){ swap(x1, x2); swap(y1, y2); } array<int, 4> nl = {x1, y1, x2, y2}; lines2[i].ss = nl; } } auto solve_vertical = [&](){ sort(all(lines)); vector<array<int, 4>> ans; FOR(i, 1, n, 1){ ans.pb({lines[i].ff, lines[i].ss.ff, lines[i - 1].ff, lines[i - 1].ss.ss}); } REP(i, n - 1){ REP(j, 4){ cout << ans[i][j] << (j == 3 ? "\n" : " "); } } }; auto solve_parallel = [&](){ sort(all(lines2)); vector<array<int, 4>> ans; FOR(i, 1, n , 1){ ans.pb({lines2[i].ss[0], lines2[i].ss[1], lines2[i - 1].ss[2], lines2[i - 2].ss[3]}); } REP(i, n - 1){ REP(j, 4){ cout << ans[i][j] << (j == 3 ? "\n" : " "); } } }; if(vertical) solve_vertical(); else{ solve_parallel(); } 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...