이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
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 |
---|
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... |