#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const long long mxn = 1e6 + 10,mxi = 2e7 + 10;
double cxx;
struct sett
{
double stx,sty,slo;
long long num;
bool operator () (const struct sett &l,const struct sett &r)const
{
return (l.sty + (cxx - l.stx) * l.slo) < (r.sty + (cxx - r.stx) * r.slo);
// return l.sty > r.sty;
}
};
struct we
{
long long xx,yy,sta,num,bey;
double slo,soo;
};
bool cmp(const struct we &l,const struct we &r)
{
// if(l.soo - r.soo > 0.0000001 || l.soo - r.soo < -0.0000001)
// // if(l.soo != r.soo)
// return l.soo < r.soo;
if(l.xx != r.xx)
return l.xx < r.xx;
return l.yy < r.yy;
}
set<struct sett,struct sett> see;
struct we ta[mxn] = {};
long long nux[mxn] = {},nuy[mxn] = {};
int main()
{
long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
set<struct sett>::iterator cit,fit;
double t,p,cslo,cx,cy;
scanf("%lld",&n);
for(i=0; i<n; i++)
{
scanf("%lld %lld %lld %lld",&cn,&cm,&fn,&fm);
if(cn > fn || (cn == fn && cm > fm))
{
f = cn;
cn = fn;
fn = f;
f = cm;
cm = fm;
fm = f;
}
if(fn - cn == 0)
{
// sta = 1;
cslo = mxi;
// cslo = mxi;
}
else
{
t = fm - cm;
p = fn - cn;
// ta[i].slo = t / p;
cslo = t/p;
}
ta[i*2] = {cn,cm,0,i,0,cslo,0};
ta[i*2+1] = {fn,fm,1,i,cm,cslo,0};
}
sort(ta,ta+n*2,cmp);
see.insert({-mxi,-mxi,0,n});
of = 0;
printf("\n");
for(i=0; i<2*n; i++)
{
cxx = ta[i].xx;
cx = cxx;
cy = ta[i].yy;
if(ta[i].sta == 0)
{
cn = (*prev(see.upper_bound({cx,cy,0,0}))).num;
if(cn == n && of == 0)
{
of = 1;
}
else
{
printf("%lld %lld %.0lf %.0lf\n",nux[cn],nuy[cn],cx,cy);
}
nux[cn] = cx;
nuy[cn] = cy;
see.insert({cx,cy,ta[i].slo,ta[i].num});
fn = ta[i].num;
nux[fn] = cx;
nuy[fn] = cy;
}
else
{
cit = prev(see.upper_bound({cx,cy+0.001,0,0}));
// cn = (*cit).num;
fit = prev(cit);
cn = (*fit).num;
see.erase(cit);
nux[cn] = cx;
nuy[cn] = cy;
}
}
// if(sta == 1)
// {
// for(i=0; i<n; i++)
// {
// ta[i].soo = ta[i].xx;
// }
// }
// else
// {
// for(i=0; i<n; i++)
// {
// t = ta[i].xx;
// f = ta[i].yy;
// ta[i].soo = f - (t * cslo);
// }
// }
// sort(ta,ta+n,cmp);
// printf("\n");
// for(i=0; i<n-1; i++)
// {
// // if(ta[i].soo != ta[i+1].soo)
// // {
// // printf("%lld %lld %lld %lld\n",ta[i].xx,ta[i].yy,ta[i+1].xx,ta[i+1].yy);
// // }
// // else
// // {
// printf("%lld %lld %lld %lld\n",ta[i].xx2,ta[i].yy2,ta[i+1].xx,ta[i+1].yy);
// // }
// }
return 0;
}
Compilation message
roads.cpp: In function 'int main()':
roads.cpp:39:17: warning: unused variable 'j' [-Wunused-variable]
39 | long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
| ^
roads.cpp:39:21: warning: unused variable 'm' [-Wunused-variable]
39 | long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
| ^
roads.cpp:39:37: warning: unused variable 'sta' [-Wunused-variable]
39 | long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
| ^~~
roads.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%lld",&n);
| ~~~~~^~~~~~~~~~~
roads.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%lld %lld %lld %lld",&cn,&cm,&fn,&fm);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
58 ms |
6608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
14 ms |
2100 KB |
Output is correct |
5 |
Correct |
32 ms |
3864 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 |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
17 ms |
2132 KB |
Output is correct |
5 |
Correct |
26 ms |
3940 KB |
Output is correct |
6 |
Correct |
1 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 |
14 ms |
2168 KB |
Output is correct |
10 |
Correct |
161 ms |
18620 KB |
Output is correct |
# |
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 |
396 KB |
Output is correct |
4 |
Correct |
14 ms |
2176 KB |
Output is correct |
5 |
Correct |
26 ms |
3904 KB |
Output is correct |
6 |
Correct |
1 ms |
312 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
14 ms |
2040 KB |
Output is correct |
10 |
Correct |
82 ms |
9400 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
304 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
13 ms |
2132 KB |
Output is correct |
6 |
Correct |
0 ms |
340 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 |
2068 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
13 ms |
2132 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
316 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
7 ms |
960 KB |
Output is correct |
23 |
Correct |
6 ms |
1108 KB |
Output is correct |
24 |
Correct |
11 ms |
1492 KB |
Output is correct |
25 |
Correct |
0 ms |
224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
60 ms |
6676 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
14 ms |
2128 KB |
Output is correct |
7 |
Correct |
35 ms |
3912 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
452 KB |
Output is correct |
11 |
Correct |
19 ms |
2120 KB |
Output is correct |
12 |
Correct |
161 ms |
18612 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
14 ms |
2160 KB |
Output is correct |
17 |
Correct |
79 ms |
9504 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
320 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
7 ms |
852 KB |
Output is correct |
27 |
Correct |
6 ms |
852 KB |
Output is correct |
28 |
Correct |
11 ms |
1492 KB |
Output is correct |
29 |
Correct |
90 ms |
12020 KB |
Output is correct |
30 |
Correct |
118 ms |
17148 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
112 ms |
12512 KB |
Output is correct |
33 |
Correct |
127 ms |
12476 KB |
Output is correct |
34 |
Correct |
135 ms |
16588 KB |
Output is correct |
35 |
Correct |
142 ms |
17220 KB |
Output is correct |
36 |
Correct |
152 ms |
19908 KB |
Output is correct |