This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |