Submission #56829

#	Time	Username	Problem	Language	Result	Execution time	Memory
56829		dennisstar	먼 별 (KOI16_dist)	C++11	0 / 100	47 ms	1904 KiB

dist

#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=a.tx-b.tx, y=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--;
	i=0, j=t0-1;
	for (i=0; i<t0; i++) {
		while(i!=j&&cw(st[stk[i]], st[stk[(i+1)%t1]], st[stk[j]], st[stk[(j+1)%t1]])>=0) j=(j+1)%t1;
		if (i==j)j=(j+1)%t1;
		mx=std::max(mx,dist(st[stk[i]], st[stk[j]]));
	}
	return mx;
}
void TriS()
{
	int st=0, re=T;
	int x1, x2;
	long long d1, d2;
	while(st<=re) {
		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-1;
		if (d1>=d2) st=x1+1;
		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 (stderr)

dist.cpp: In function 'int main()':
dist.cpp:77: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:78: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);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 40
• Subtask 3: 0 / 39
• Subtask 4: 0 / 19