#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;
bool cmp(pair<pair<ll,ll>,pair<ll,ll>>&l,pair<pair<ll,ll>,pair<ll,ll>>&r){
return l.fr.fr/l.fr.sc<r.fr.fr/r.fr.sc;
}
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]);
}
vector<pair<pair<ll,ll>,pair<ll,ll>>>vec;
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);
vec.push_back(make_pair(tmp.fr,b[0]));
}
sort(vec.begin(),vec.end(),cmp);
for(int i=1;i<vec.size();i++)printf("%lld %lld %lld %lld\n",vec[i-1].sc.fr,vec[i-1].sc.sc,vec[i].sc.fr,vec[i].sc.sc);
}
}
Compilation message
roads.cpp: In function 'int main()':
roads.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=1;i<vec.size();i++)printf("%lld %lld %lld %lld\n",vec[i-1].sc.fr,vec[i-1].sc.sc,vec[i].sc.fr,vec[i].sc.sc);
| ~^~~~~~~~~~~
roads.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
roads.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf("%lld%lld%lld%lld",&a[i].fr,&a[i].sc,&b[i].fr,&b[i].sc);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
11 ms |
1984 KB |
Output is correct |
5 |
Correct |
25 ms |
3656 KB |
Output is correct |
# |
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 |
11 ms |
2004 KB |
Output is correct |
5 |
Correct |
23 ms |
3620 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
16 ms |
2512 KB |
Output is correct |
10 |
Failed |
209 ms |
22112 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])" |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1980 KB |
Output is correct |
5 |
Correct |
24 ms |
3600 KB |
Output is correct |
6 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
2 |
Halted |
0 ms |
0 KB |
- |