Submission #57737

#TimeUsernameProblemLanguageResultExecution timeMemory
57737gs18081먼 별 (KOI16_dist)C++11
0 / 100
211 ms3064 KiB
#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 a.first*b.second - a.second * b.first +b.first * c.second - b.second * c.first +c.first * a.second - c.second * 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){ vector<pi> dots; 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){ return delta(dots[0],a,b)==0?absdist(dots[0],a)<absdist(dots[0],b) : delta(dots[0],a,b)>0; }); vector<pi> hull; 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; 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+1; if(v0<ans||(v0==ans&&m0<day)){ ans=v0; day=m0; } } else { e=m1-1; if(v1<ans||(v1==ans&&m1<day)){ ans=v1; day=m1; } } } if(e<s) swap(s,e); /*/ if(T<=20){ s=0; e=20; } /*/ for(int i=s;i<=e;i++){ if(ans>maxdist(i)||(ans==maxdist(i)&&i<day)){ day=i; ans=maxdist(i); } } printf("%d\n%lld\n",day,ans); return 0; }

Compilation message (stderr)

dist.cpp: In function 'll maxdist(int)':
dist.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<dots.size();i++){
              ~^~~~~~~~~~~~
dist.cpp:50: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:63: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:65: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...