Submission #56967

#	Time	Username	Problem	Language	Result	Execution time	Memory
56967		dennisstar	먼 별 (KOI16_dist)	C++11	0 / 100	536 ms	2028 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=(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 (stderr)

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);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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