#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
struct frac{
pll a;
frac(ll n, ll d){
ll g = gcd(abs(n),abs(d));
n /= g, d /= g;
if(d < 0){
d = -d;
n = -n;
}
else if(d == 0){
n = 1;
}
a = {n,d};
}
bool operator<(const frac &f) const {
auto [x1,y1] = a;
auto [x2,y2] = f.a;
return x1*y2 < x2*y1;
}
};
void solve(int test_case)
{
ll n; cin >> n;
map<frac,vector<pll>> mp;
frac curr_gradient(1,1);
rep1(i,n){
ll x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
frac gradient(y2-y1,x2-x1);
if(i == 1) curr_gradient = gradient;
else assert(gradient.a == curr_gradient.a);
frac y_intercept(y1*(x2-x1)-x1*(y2-y1),x2-x1);
mp[y_intercept].pb({x1,y1});
mp[y_intercept].pb({x2,y2});
}
vector<array<ll,4>> ans;
for(auto it = mp.begin(); it != mp.end(); ++it){
auto &v = it->second;
sort(all(v));
// assert(!(sz(v)&1));
if(it != mp.begin()){
auto it2 = prev(it);
ans.pb({it2->second[0].ff,v[0].ff,it2->second[0].ss,v[0].ss});
}
for(int i = 1; i < sz(v)-1; i += 2){
ans.pb({v[i].ff,v[i].ss,v[i+1].ff,v[i+1].ss});
}
}
for(auto [x1,y1,x2,y2] : ans){
cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
}
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
8 ms |
1752 KB |
Output is correct |
5 |
Correct |
14 ms |
3032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
7 ms |
1748 KB |
Output is correct |
5 |
Correct |
14 ms |
3028 KB |
Output is correct |
6 |
Failed |
0 ms |
344 KB |
Condition failed: "iA != P2I.end()" |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
612 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
7 ms |
1756 KB |
Output is correct |
5 |
Correct |
15 ms |
3032 KB |
Output is correct |
6 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |