| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56967 |
2018-07-13T11:19:32 Z |
dennisstar |
None (KOI16_dist) |
C++11 |
|
536 ms |
2028 KB |
#include <bits/stdc++.h>
#define round(x) (int)(x+0.5)
typedef long long LL;
int N, T;
int anst;
LL mxd=((1ll<<62)-1)*2+1;
int stk[60010];
struct data
{
int x, y, dx, dy;
int tx, ty;
bool operator <(const data &r)const {return tx==r.tx?ty<r.ty:tx<r.tx;}
}st[30010];
int cw(data a, data b, data c)
{
LL ii=(LL)(b.x-a.x)*(c.y-a.y)-(LL)(c.x-a.x)*(b.y-a.y);
return ii>0?1:ii==0?0:-1;
}
int cw(data a, data b, data c, data d)
{
LL ii=(LL)(d.y-c.y)*(b.x-a.x)-(LL)(b.y-a.y)*(d.x-c.x);
return ii>0?1:ii==0?0:-1;
}
long long dist(data a, data b)
{
LL x=(LL)a.tx-b.tx, y=(LL)a.ty-b.ty;
return x*x+y*y;
}
long long rtc(int T)
{
int i, j;
for (i=0; i<N; i++) st[i].tx=st[i].x+T*st[i].dx, st[i].ty=st[i].y+T*st[i].dy;
std::sort(st, st+N);
int t0=1, t1;
stk[0]=0;
long long mx=0;
for (i=1; i<N; i++) {
while(t0>1&&cw(st[stk[t0-2]], st[stk[t0-1]], st[i])<=0) t0--;
stk[t0++]=i;
}
t1=t0;
for (i=N-1; i>=0; i--) {
while(t1>t0&&cw(st[stk[t1-2]], st[stk[t1-1]], st[i])<=0) t1--;
stk[t1++]=i;
}
t1--;
int ii=0; j=t0-1;
//여기부터
int xx1, yy1, xx2, yy2;
LL cos1, cos2;
int x1, x2, y1, y2;
x1=x2=0, y1=-1, y2=1;
for (i=0; i<t1; i++) {
mx=std::max(mx, dist(st[stk[ii]],st[stk[j]]));
xx1=st[stk[(ii+1)%t1]].tx-st[stk[ii]].tx, xx2=st[stk[(j+1)%t1]].tx-st[stk[j]].tx;
yy1=st[stk[(ii+1)%t1]].ty-st[stk[ii]].ty, yy2=st[stk[(j+1)%t1]].ty-st[stk[j]].ty;
cos1=(x1*xx1+y1*yy1)*(x1*xx1+y1*yy1)*(x2*x2+y2*y2)*(xx2*xx2+yy2*yy2);
cos2=(x2*xx2+y2*yy2)*(x2*xx2+y2*yy2)*(x1*x1+y1*y1)*(xx1*xx1+yy1*yy1);
if(cos1>cos2) {
ii=(ii+1)%t1;
x1=xx1,y1=yy1;
x2=-x1,y2=-y1;
}
else {
j=(j+1)%t1;
x2=xx2,y2=yy2;
x1=-x2,y1=-y2;
}
}
//여기까지
return mx;
}
void TriS()
{
int st=0, re=T;
int x1, x2;
long long d1, d2;
for(int i=0; i<100; i++) {
x1=round(((double)st*2+(double)re)/3);
x2=round(((double)st+(double)re*2)/3);
d1=rtc(x1);
d2=rtc(x2);
if (d1<=d2) re=x2;
if (d1>=d2) st=x1;
if (mxd>d1) { mxd=d1; anst=x1;}
if (mxd==d1) anst=std::min(anst,x1);
if (mxd>d2) { mxd=d2; anst=x2;}
if (mxd==d2) anst=std::min(anst,x2);
}
}
int main()
{
// freopen("input.txt", "r", stdin);
int i;
scanf("%d %d", &N, &T);
for(i=0; i<N; i++) scanf("%d %d %d %d", &st[i].x, &st[i].y, &st[i].dx, &st[i].dy);
TriS();
printf("%d\n%lld", anst, mxd);
return 0;
}
Compilation message
dist.cpp: In function 'int main()':
dist.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &T);
~~~~~^~~~~~~~~~~~~~~~~
dist.cpp:96:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=0; i<N; i++) scanf("%d %d %d %d", &st[i].x, &st[i].y, &st[i].dx, &st[i].dy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
536 ms |
2028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
