Submission #57753

#	Time	Username	Problem	Language	Result	Execution time	Memory
57753		red1108	먼 별 (KOI16_dist)	C++17	2 / 100	222 ms	2812 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];



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

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