# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
57755 |
2018-07-16T02:13:15 Z |
gs18081 |
None (KOI16_dist) |
C++11 |
|
717 ms |
6176 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
struct star{
ll x,y,dx,dy;
};
int N,T;
star stars[40000];
vector<pi> dots;
vector<pi> hull;
ll myabs(ll num){
return num>0?num:-num;
}
ll delta(pi a,pi b,pi c){
/*return a.first*b.second - a.second * b.first
+b.first * c.second - b.second * c.first
+c.first * a.second - c.second * a.first;
*/
return (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first);
}
ll dist(pi a,pi b){
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
ll absdist(pi a,pi b){
return myabs(a.first-b.first)+myabs(a.second-b.second);
}
ll maxdist(int day){
dots.clear();
for(int i=0;i<N;i++){
dots.push_back(pi(stars[i].x+day*stars[i].dx,stars[i].y+stars[i].dy*day));
}
sort(dots.begin(),dots.end(),[&](pi a,pi b){
return a.second==b.second?a.first<b.first:a.second<b.second;
});
dots.erase(unique(dots.begin(),dots.end()),dots.end());
sort(dots.begin()+1,dots.end(),[&](pi a,pi b){
/*/
if(delta(dots[0],a,b)==0){
if(a.first==b.first) return a.second<b.second;
return a.first<b.first;
}
return delta(dots[0],a,b)>0;
//*/
return delta(dots[0],a,b)==0?absdist(dots[0],a)<absdist(dots[0],b) : delta(dots[0],a,b)>0;
});
hull.clear();
hull.push_back(dots[0]);
for(int i=1;i<dots.size();i++){
while(hull.size()>=2&&delta(hull[hull.size()-2],hull.back(),dots[i])<=0) hull.pop_back();
hull.push_back(dots[i]);
}
ll ret=0;
int j=1%hull.size();
for(int i=0;i<hull.size();i++){
int ni=(i+1)%hull.size();
for(;;){
int nj=(j+1)%hull.size();
if(delta(pi(0,0),pi(hull[ni].first-hull[i].first,hull[ni].second-hull[i].second),pi(hull[nj].first-hull[j].first,hull[nj].second-hull[j].second))<=0)
break;
j=nj;
}
ret=max(ret,dist(hull[i],hull[j]));
}
return ret;
}
int main(){
scanf("%d %d",&N,&T);
for(int i=0;i<N;i++){
scanf("%lld %lld %lld %lld",&stars[i].x,&stars[i].y,&stars[i].dx,&stars[i].dy);
}
int s=0;
int e=T;
ll ans=maxdist(0);
int day=0;
while(s+5<e){
int m0=(s*2+e)/3;
int m1=(s+e*2)/3;
ll v0=maxdist(m0);
ll v1=maxdist(m1);
if(v0>v1) {
s=m0;
}
else
{
e=m1;
}
}
if(e<s) swap(s,e);
//*/
if(T<=20){
s=0;
e=T;
}
//*/
for(int i=s;i<=e;i++){
if(ans>maxdist(i)||(ans==maxdist(i)&&i<day)){
day=i;
ans=maxdist(i);
}
}
/*/
if(day==278315){
printf("%d00",T);
for(int i=0;i<N;i++){
printf("%d00%d00%d00%d00",stars[i].x,stars[i].y,stars[i].dx,stars[i].dy);
}
}
//*/
printf("%d\n%lld\n",day,ans);
return 0;
}
/*
2 10000000
1453086 3632715 -20 -50
339822 849555 -16 -40
*/
Compilation message
dist.cpp: In function 'll maxdist(int)':
dist.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<dots.size();i++){
~^~~~~~~~~~~~
dist.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<hull.size();i++){
~^~~~~~~~~~~~
dist.cpp: In function 'int main()':
dist.cpp:72: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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld %lld",&stars[i].x,&stars[i].y,&stars[i].dx,&stars[i].dy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
2 ms |
488 KB |
Output is correct |
5 |
Correct |
2 ms |
488 KB |
Output is correct |
6 |
Correct |
2 ms |
524 KB |
Output is correct |
7 |
Correct |
3 ms |
524 KB |
Output is correct |
8 |
Correct |
3 ms |
536 KB |
Output is correct |
9 |
Correct |
2 ms |
536 KB |
Output is correct |
10 |
Correct |
2 ms |
536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
2 ms |
488 KB |
Output is correct |
5 |
Correct |
2 ms |
488 KB |
Output is correct |
6 |
Correct |
2 ms |
524 KB |
Output is correct |
7 |
Correct |
3 ms |
524 KB |
Output is correct |
8 |
Correct |
3 ms |
536 KB |
Output is correct |
9 |
Correct |
2 ms |
536 KB |
Output is correct |
10 |
Correct |
2 ms |
536 KB |
Output is correct |
11 |
Correct |
18 ms |
592 KB |
Output is correct |
12 |
Correct |
19 ms |
592 KB |
Output is correct |
13 |
Correct |
19 ms |
592 KB |
Output is correct |
14 |
Correct |
19 ms |
620 KB |
Output is correct |
15 |
Correct |
15 ms |
620 KB |
Output is correct |
16 |
Correct |
16 ms |
620 KB |
Output is correct |
17 |
Correct |
16 ms |
624 KB |
Output is correct |
18 |
Correct |
5 ms |
624 KB |
Output is correct |
19 |
Correct |
16 ms |
636 KB |
Output is correct |
20 |
Correct |
18 ms |
636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
431 ms |
2168 KB |
Output is correct |
2 |
Correct |
419 ms |
2804 KB |
Output is correct |
3 |
Correct |
401 ms |
3208 KB |
Output is correct |
4 |
Correct |
411 ms |
4380 KB |
Output is correct |
5 |
Correct |
327 ms |
4512 KB |
Output is correct |
6 |
Correct |
388 ms |
5668 KB |
Output is correct |
7 |
Correct |
404 ms |
5668 KB |
Output is correct |
8 |
Correct |
111 ms |
5668 KB |
Output is correct |
9 |
Correct |
413 ms |
6172 KB |
Output is correct |
10 |
Correct |
422 ms |
6172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
2 ms |
488 KB |
Output is correct |
5 |
Correct |
2 ms |
488 KB |
Output is correct |
6 |
Correct |
2 ms |
524 KB |
Output is correct |
7 |
Correct |
3 ms |
524 KB |
Output is correct |
8 |
Correct |
3 ms |
536 KB |
Output is correct |
9 |
Correct |
2 ms |
536 KB |
Output is correct |
10 |
Correct |
2 ms |
536 KB |
Output is correct |
11 |
Correct |
18 ms |
592 KB |
Output is correct |
12 |
Correct |
19 ms |
592 KB |
Output is correct |
13 |
Correct |
19 ms |
592 KB |
Output is correct |
14 |
Correct |
19 ms |
620 KB |
Output is correct |
15 |
Correct |
15 ms |
620 KB |
Output is correct |
16 |
Correct |
16 ms |
620 KB |
Output is correct |
17 |
Correct |
16 ms |
624 KB |
Output is correct |
18 |
Correct |
5 ms |
624 KB |
Output is correct |
19 |
Correct |
16 ms |
636 KB |
Output is correct |
20 |
Correct |
18 ms |
636 KB |
Output is correct |
21 |
Correct |
431 ms |
2168 KB |
Output is correct |
22 |
Correct |
419 ms |
2804 KB |
Output is correct |
23 |
Correct |
401 ms |
3208 KB |
Output is correct |
24 |
Correct |
411 ms |
4380 KB |
Output is correct |
25 |
Correct |
327 ms |
4512 KB |
Output is correct |
26 |
Correct |
388 ms |
5668 KB |
Output is correct |
27 |
Correct |
404 ms |
5668 KB |
Output is correct |
28 |
Correct |
111 ms |
5668 KB |
Output is correct |
29 |
Correct |
413 ms |
6172 KB |
Output is correct |
30 |
Correct |
422 ms |
6172 KB |
Output is correct |
31 |
Correct |
656 ms |
6172 KB |
Output is correct |
32 |
Correct |
614 ms |
6172 KB |
Output is correct |
33 |
Correct |
622 ms |
6172 KB |
Output is correct |
34 |
Correct |
647 ms |
6172 KB |
Output is correct |
35 |
Correct |
525 ms |
6172 KB |
Output is correct |
36 |
Correct |
717 ms |
6172 KB |
Output is correct |
37 |
Correct |
572 ms |
6172 KB |
Output is correct |
38 |
Correct |
125 ms |
6172 KB |
Output is correct |
39 |
Correct |
530 ms |
6172 KB |
Output is correct |
40 |
Correct |
667 ms |
6172 KB |
Output is correct |
41 |
Correct |
632 ms |
6172 KB |
Output is correct |
42 |
Correct |
649 ms |
6176 KB |
Output is correct |