This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//빛 민준
#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];
ll myabs(ll num){
return num>0?num:-num;
}
ll delta(pi a,pi b,pi c){
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);
}
vector<pi> dots;
vector<pi> hull;
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]);
}
if(hull.size()<=1) return 0;
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,x1,x2;
while(s+5<e){
x1=((ll)2*s+e)/3;
x2=((ll)2*e+s)/3;
if(maxdist(x1)>maxdist(x2)) s=x1;
else e=x2;
}
if(e<s) swap(s,e);
if(T<=20){
s=0;
e=T;
}
ans=maxdist(s);
day=s;
for(int i=s+1;i<=e;i++){
if(ans>maxdist(i)){
day=i;
ans=maxdist(i);
}
}
printf("%d\n%lld\n",day,ans);
}
Compilation message (stderr)
dist.cpp: In function 'll maxdist(int)':
dist.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<dots.size();i++){
~^~~~~~~~~~~~
dist.cpp:56: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:69: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:71: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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |