답안 #97376 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97376	2019-02-15T14:54:32 Z	fefe	먼 별 (KOI16_dist)	C++17	100 / 100	764 ms	2552 KB

dist

#include<bits/stdc++.h>
#define MAX_N 30005
#define MAX_M 100005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))

#define next(x) (((x)+1)%m)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;

//plz write LL
// 2 <= N <= 3*(1e4) (sp N == 2)
// 0 <= T <= 1e7
//input : N,T
//input : x,y,dx,dy
// -1e7 <= x,y <= 1e7
//  -1e2 <= dx,dy <= 1e2
LL n;
LL X[MAX_N],Y[MAX_N],dx[MAX_N],dy[MAX_N];
pil V[MAX_N];
LL ccw(LL xx,LL xy,LL yx,LL yy,LL zx,LL zy){return (xx*yy+yx*zy+zx*xy)-(xy*yx+yy*zx+zy*xx);}
LL get_val(LL t){//return max_distance
	LL i;
	for(i=0;i<n;i++)	V[i] = {X[i]+dx[i]*t,Y[i]+dy[i]*t};
	for(i=1;i<n;i++){
		if(V[0]>V[i])	swap(V[0],V[i]);
	}
	sort(V+1,V+n,[&](const pil x,const pil y){
		if(ccw(x.fi,x.se,V[0].fi,V[0].se,y.fi,y.se)==0)	return sq(x.fi-V[0].fi)+sq(x.se-V[0].se)<sq(y.fi-V[0].fi)+sq(y.se-V[0].se);
		return (ccw(x.fi,x.se,V[0].fi,V[0].se,y.fi,y.se)>0);
	});
	LL m=2;
	for(i=2;i<n;i++){
		while(m>1 && ccw(V[m-2].fi,V[m-2].se,V[m-1].fi,V[m-1].se,V[i].fi,V[i].se)>=0)	m--;
		V[m++]=V[i];
	}
	if(m==2)	return sq(V[0].fi-V[1].fi)+sq(V[0].se-V[1].se);
	LL x=1,mx=0;
	for(i=0;i<m;i++){
		while(ccw(V[next(i)].fi,V[next(i)].se,V[i].fi,V[i].se,V[i].fi+V[x].fi-V[next(x)].fi,V[i].se+V[x].se-V[next(x)].se)<0)	x=next(x);
		mx=max(mx,sq(V[i].fi-V[x].fi)+sq(V[i].se-V[x].se));
	}
	return mx;
}
int main(){
	LL i,l,r;
	scanf("%lld %lld",&n,&r);
	for(i=0;i<n;i++)	scanf("%lld %lld %lld %lld",&X[i],&Y[i],&dx[i],&dy[i]);
	l=0;
	while(l+1<r){
		LL m1=(2*l+r)/3,m2=(l+2*r)/3;
		LL x=get_val(m1),y=get_val(m2);
		if(x>y)	l=m1+1;	
		else	r=m2-1;
	}
	LL x=get_val(l),y=get_val(r);
	if(y<x)	printf("%lld\n%lld\n",r,y);
	else	printf("%lld\n%lld\n",l,x);
	return 0;
}

Compilation message

dist.cpp: In function 'int main()':
dist.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&r);
  ~~~~~^~~~~~~~~~~~~~~~~~~
dist.cpp:66:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=0;i<n;i++) scanf("%lld %lld %lld %lld",&X[i],&Y[i],&dx[i],&dy[i]);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct

Subtask #2
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	10 ms	512 KB	Output is correct
12	Correct	12 ms	384 KB	Output is correct
13	Correct	10 ms	384 KB	Output is correct
14	Correct	11 ms	512 KB	Output is correct
15	Correct	10 ms	360 KB	Output is correct
16	Correct	27 ms	384 KB	Output is correct
17	Correct	8 ms	484 KB	Output is correct
18	Correct	6 ms	384 KB	Output is correct
19	Correct	8 ms	384 KB	Output is correct
20	Correct	12 ms	384 KB	Output is correct

Subtask #3
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	1656 KB	Output is correct
2	Correct	111 ms	2296 KB	Output is correct
3	Correct	91 ms	2316 KB	Output is correct
4	Correct	91 ms	2432 KB	Output is correct
5	Correct	79 ms	2452 KB	Output is correct
6	Correct	109 ms	2336 KB	Output is correct
7	Correct	52 ms	2176 KB	Output is correct
8	Correct	48 ms	2168 KB	Output is correct
9	Correct	74 ms	2552 KB	Output is correct
10	Correct	71 ms	2424 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	10 ms	512 KB	Output is correct
12	Correct	12 ms	384 KB	Output is correct
13	Correct	10 ms	384 KB	Output is correct
14	Correct	11 ms	512 KB	Output is correct
15	Correct	10 ms	360 KB	Output is correct
16	Correct	27 ms	384 KB	Output is correct
17	Correct	8 ms	484 KB	Output is correct
18	Correct	6 ms	384 KB	Output is correct
19	Correct	8 ms	384 KB	Output is correct
20	Correct	12 ms	384 KB	Output is correct
21	Correct	90 ms	1656 KB	Output is correct
22	Correct	111 ms	2296 KB	Output is correct
23	Correct	91 ms	2316 KB	Output is correct
24	Correct	91 ms	2432 KB	Output is correct
25	Correct	79 ms	2452 KB	Output is correct
26	Correct	109 ms	2336 KB	Output is correct
27	Correct	52 ms	2176 KB	Output is correct
28	Correct	48 ms	2168 KB	Output is correct
29	Correct	74 ms	2552 KB	Output is correct
30	Correct	71 ms	2424 KB	Output is correct
31	Correct	372 ms	2472 KB	Output is correct
32	Correct	424 ms	2424 KB	Output is correct
33	Correct	396 ms	2396 KB	Output is correct
34	Correct	366 ms	2552 KB	Output is correct
35	Correct	439 ms	2552 KB	Output is correct
36	Correct	764 ms	2296 KB	Output is correct
37	Correct	347 ms	2424 KB	Output is correct
38	Correct	264 ms	2464 KB	Output is correct
39	Correct	322 ms	2472 KB	Output is correct
40	Correct	403 ms	2484 KB	Output is correct
41	Correct	452 ms	2524 KB	Output is correct
42	Correct	428 ms	2552 KB	Output is correct

답안 #97376

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 40.0 / 40.0

Subtask #3 39.0 / 39.0

Subtask #4 19.0 / 19.0

Subtask #1
2.0 / 2.0

Subtask #2
40.0 / 40.0

Subtask #3
39.0 / 39.0

Subtask #4
19.0 / 19.0