Submission #57755

#	Time	Username	Problem	Language	Result	Execution time	Memory
57755		gs18081	먼 별 (KOI16_dist)	C++11	100 / 100	717 ms	6176 KiB

dist

#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 (stderr)

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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 40 / 40
• Subtask 3: 39 / 39
• Subtask 4: 19 / 19