Submission #667632

#TimeUsernameProblemLanguageResultExecution timeMemory
667632dozerRoads (CEOI20_roads)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define pb push_back #define endl "\n" #define sp " " #define pii pair<int, int> #define st first #define nd second #define N 100005 #define L(node) node * 2 #define R(node) node * 2 + 1 #define int long long const int INF = 1e9 + 7; const int modulo = 1e9 + 7; int adj[N], done[N]; double x[N], y[N]; int ox[N], oy[N]; int32_t main() { //fileio(); fastio(); int n; cin>>n; vector<int> vec; int a, b; for (int i = 1; i <= n; i++) { int x1, x2, y1, y2; cin>>x1>>y1>>x2>>y2; a = x1 - x2; b = y1 - y2; int u = 2 * i - 1, v = 2 * i; x[u] = x1, y[u] = y1; x[v] = x2, y[v] = y2; adj[u] = v; adj[v] = u; vec.pb(u); vec.pb(v); } //cout<<a<<sp<<b<<endl; double hyp = sqrt(a * a + b * b); for (int i = 1; i <= 2 * n; i++) { ox[i] = x[i], oy[i] = y[i]; if (x[i] == y[i] && x[i] == 0) continue; double hyp2 = sqrt(x[i] * x[i] + y[i] * y[i]); double cos = x[i] / hyp2, sin = y[i] / hyp2; //cout<<hyp<<sp<<hyp2<<sp<<cos<<sp<<sin<<endl; y[i] = hyp2 * ((a / hyp) * sin + cos * (b / hyp)); x[i] = hyp2 * ((a / hyp) * cos - sin * (b / hyp)); //cout<<x[i]<<sp<<y[i]<<endl; } sort(vec.begin(), vec.end(), [&](int a, int b){ return make_pair(y[a], x[a]) < make_pair(y[b], x[b]); }); for (auto i : vec) cout<<i<<sp; cout<<endl; vector<array<int, 4>> ans; set<pair<pair<double, double>, int>> s; done[adj[vec.front()]] = 1; for (auto i : vec) { if (done[i] == 0 && !s.empty()) { //cout<<i<<endl; auto it = s.lower_bound({{x[i], (double)-modulo}, 0}); if (it == s.end()) it--; pair<double, double> tmp = it->st; int ind = it->nd; ans.pb({ox[i], oy[i], ox[ind], oy[ind]}); done[i] = 1; done[adj[i]] = 1; } s.insert({{x[i], -y[i]}, i}); } for (auto i : ans) { for (int j = 0; j < 4; j++) cout<<i[j]<<sp; cout<<endl; } cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n"; }

Compilation message (stderr)

roads.cpp: In function 'int32_t main()':
roads.cpp:75:25: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
   75 |    pair<double, double> tmp = it->st;
      |                         ^~~
roads.cpp:48:30: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |  double hyp = sqrt(a * a + b * b);
      |                            ~~^~~
roads.cpp:48:22: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |  double hyp = sqrt(a * a + b * b);
      |                    ~~^~~
#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...