| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 23372 |
2017-05-07T07:29:30 Z |
TAMREF |
None (KOI16_dist) |
C++11 |
|
386 ms |
3900 KB |
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int MX = 30005;
struct point{
ll x, y;
point(ll _x=0,ll _y=0):x(_x),y(_y){}
ll operator* (point z){return x*z.y-y*z.x;}
bool operator< (point z){return x<z.x||x==z.x&&y<z.y;}
point operator- (point z){return point(x-z.x,y-z.y);}
};
inline ll d(point z, point w=point(0,0)){return (z.x-w.x)*(z.x-w.x)+(z.y-w.y)*(z.y-w.y);}
point tam[MX], cv[MX], u[MX], v[MX];
int N,T,top;
void input(){
scanf("%d%d",&N,&T);
for(int i=0;i<N;i++) scanf("%lld%lld%lld%lld",&u[i].x,&u[i].y,&v[i].x,&v[i].y);
}
void graham(){
swap(tam[0],*min_element(tam,tam+N));
for(int i=N;i--;) tam[i]=tam[i]-tam[0];
sort(tam+1,tam+N,[](point m, point n){return m*n<0||m*n==0&&d(m)<d(n);});
for(int i=top=0;i<N;i++){
while(top>1&&(tam[i]-cv[top-2])*(cv[top-1]-cv[top-2])<=0) --top;
cv[top++]=tam[i];
}
}
ll RC(){
int idx=0, jdx=max_element(cv,cv+top)-cv; ll D=0; point g, h;
for(int i=0;i<top;i++){
D=max(D,d(cv[idx],cv[jdx]));
point g=cv[(idx+1)%top]-cv[idx], h=cv[(jdx+1)%top]-cv[jdx];
(++(g*h>=0?idx:jdx))%=top;
}
return D;
}
ll pro(int t){
for(int i=0;i<N;i++){
tam[i].x=u[i].x+v[i].x*t;
tam[i].y=u[i].y+v[i].y*t;
}
graham();
return RC();
}
int main(){
input();
int p=0, q, r, s=T;
while(p<s){
q=p+(s-p)/3, r=s-(s-p)/3;
if(pro(q)<=pro(r)) s=r-1;
else p=q+1;
}
printf("%d\n%lld\n",p,pro(p));
}
Compilation message
dist.cpp: In member function 'bool point::operator<(point)':
dist.cpp:11:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
bool operator< (point z){return x<z.x||x==z.x&&y<z.y;}
^
dist.cpp: In lambda function:
dist.cpp:24:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
sort(tam+1,tam+N,[](point m, point n){return m*n<0||m*n==0&&d(m)<d(n);});
^
dist.cpp: In function 'void input()':
dist.cpp:18:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&N,&T);
^
dist.cpp:19:83: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<N;i++) scanf("%lld%lld%lld%lld",&u[i].x,&u[i].y,&v[i].x,&v[i].y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 11 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 12 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 13 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 14 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 15 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 16 |
Correct |
9 ms |
3900 KB |
Output is correct |
| 17 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 18 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 19 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 20 |
Correct |
6 ms |
3900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
3900 KB |
Output is correct |
| 2 |
Correct |
53 ms |
3900 KB |
Output is correct |
| 3 |
Correct |
56 ms |
3900 KB |
Output is correct |
| 4 |
Correct |
66 ms |
3900 KB |
Output is correct |
| 5 |
Correct |
63 ms |
3900 KB |
Output is correct |
| 6 |
Correct |
69 ms |
3900 KB |
Output is correct |
| 7 |
Correct |
49 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
33 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
66 ms |
3900 KB |
Output is correct |
| 10 |
Correct |
59 ms |
3900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3900 KB |
Output is correct |
| 11 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 12 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 13 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 14 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 15 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 16 |
Correct |
9 ms |
3900 KB |
Output is correct |
| 17 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 18 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 19 |
Correct |
3 ms |
3900 KB |
Output is correct |
| 20 |
Correct |
6 ms |
3900 KB |
Output is correct |
| 21 |
Correct |
63 ms |
3900 KB |
Output is correct |
| 22 |
Correct |
53 ms |
3900 KB |
Output is correct |
| 23 |
Correct |
56 ms |
3900 KB |
Output is correct |
| 24 |
Correct |
66 ms |
3900 KB |
Output is correct |
| 25 |
Correct |
63 ms |
3900 KB |
Output is correct |
| 26 |
Correct |
69 ms |
3900 KB |
Output is correct |
| 27 |
Correct |
49 ms |
3900 KB |
Output is correct |
| 28 |
Correct |
33 ms |
3900 KB |
Output is correct |
| 29 |
Correct |
66 ms |
3900 KB |
Output is correct |
| 30 |
Correct |
59 ms |
3900 KB |
Output is correct |
| 31 |
Correct |
296 ms |
3900 KB |
Output is correct |
| 32 |
Correct |
289 ms |
3900 KB |
Output is correct |
| 33 |
Correct |
306 ms |
3900 KB |
Output is correct |
| 34 |
Correct |
293 ms |
3900 KB |
Output is correct |
| 35 |
Correct |
309 ms |
3900 KB |
Output is correct |
| 36 |
Correct |
386 ms |
3900 KB |
Output is correct |
| 37 |
Correct |
256 ms |
3900 KB |
Output is correct |
| 38 |
Correct |
149 ms |
3900 KB |
Output is correct |
| 39 |
Correct |
216 ms |
3900 KB |
Output is correct |
| 40 |
Correct |
296 ms |
3900 KB |
Output is correct |
| 41 |
Correct |
313 ms |
3900 KB |
Output is correct |
| 42 |
Correct |
293 ms |
3900 KB |
Output is correct |
