#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
pair<ll,ll>a[100005];
pair<ll,ll>b[100005];
int n;
const int inf=1e9;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld%lld",&a[i].fr,&a[i].sc,&b[i].fr,&b[i].sc);
if(a[1].fr==b[1].fr){
//VERTICAL
map<int,vector<int>>mp;
for(int i=1;i<=n;i++){
mp[a[i].fr].push_back(a[i].sc);
mp[a[i].fr].push_back(b[i].sc);
}
int prev=inf;
for(auto &tmp:mp){
int a=tmp.fr;
vector<int>&b=tmp.sc;
sort(b.begin(),b.end());
for(int i=1;i+1<(int)b.size();i+=2)
printf("%d %d %d %d\n",a,b[i],a,b[i+1]);
if(prev^inf)
printf("%d %d %d %d\n",prev,mp[prev][0],a,b[0]);
prev=a;
}
}else{
map<pair<ll,ll>,vector<pair<ll,ll>>>mp;
for(int i=1;i<=n;i++){
pair<ll,ll>cur;
ll &x0=a[i].fr;
ll &x1=b[i].fr;
ll &y0=a[i].sc;
ll &y1=b[i].sc;
cur=make_pair(x0*y1-x1*y0,x0-x1);
if(cur.sc<0){
cur.fr*=-1;
cur.sc*=-1;
}
ll tmp=__gcd(abs(cur.fr),cur.sc);
cur.fr/=tmp;
cur.sc/=tmp;
mp[cur].push_back(a[i]);
mp[cur].push_back(b[i]);
}
pair<ll,ll>prev=make_pair(inf,inf);
for(auto &tmp:mp){
vector<pair<ll,ll>>&b=tmp.sc;
sort(b.begin(),b.end());
for(int i=1;i+1<(int)b.size();i+=2)
printf("%lld %lld %lld %lld\n",b[i].fr,b[i].sc,b[i+1].fr,b[i+1].sc);
if(prev.sc^inf)
printf("%lld %lld %lld %lld\n",prev.fr,prev.sc,b[0].fr,b[0].sc);
prev=b[0];
}
}
}
Compilation message
roads.cpp: In function 'int main()':
roads.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
roads.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%lld%lld%lld%lld",&a[i].fr,&a[i].sc,&b[i].fr,&b[i].sc);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Failed |
0 ms |
212 KB |
Condition failed: "!Cross(S[*pi], S[*pa])" |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
18 ms |
1960 KB |
Output is correct |
5 |
Correct |
28 ms |
3644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
12 ms |
1996 KB |
Output is correct |
5 |
Correct |
25 ms |
3788 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Failed |
2 ms |
468 KB |
Condition failed: "!Cross(S[*pi], S[*pa])" |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
12 ms |
1988 KB |
Output is correct |
5 |
Correct |
24 ms |
3716 KB |
Output is correct |
6 |
Failed |
1 ms |
212 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Failed |
1 ms |
212 KB |
Condition failed: "!Cross(S[*pi], S[*pa])" |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Failed |
0 ms |
212 KB |
Condition failed: "!Cross(S[*pi], S[*pa])" |
2 |
Halted |
0 ms |
0 KB |
- |