| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 97374 |
2019-02-15T14:43:07 Z |
fefe |
None (KOI16_dist) |
C++17 |
|
65 ms |
1656 KB |
#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 prev(x) (((x)-1+m)%m)
#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){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:63: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:64: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 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 |
2 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 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 |
2 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 |
Incorrect |
10 ms |
460 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 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 |
2 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 |
Incorrect |
10 ms |
460 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
