Submission #154820

#	Time	Username	Problem	Language	Result	Execution time	Memory
154820		aer0park	먼 별 (KOI16_dist)	C++14	100 / 100	419 ms	3484 KiB

dist

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct Star{
	ll x, y, dx, dy;
	void get(){
		cin >> x >> y >> dx >> dy;
	}
};

int n, t;
vector<Star> v;
vector<p> arr;

int ccw(p a, p b, p c){
	ll res = (a.first*b.second) + (b.first*c.second) + (c.first*a.second);
	res -= (b.first*a.second) + (c.first*b.second) + (a.first*c.second);
	if(res > 0) return 1;
	if(res) return -1;
	return 0;
}

ll dist(p a, p b){
	ll dx = a.first - b.first;
	ll dy = a.second - b.second;
	return dx*dx + dy*dy;
}

bool chk(p s, p e, p ss, p ee){
	p t = {e.first - s.first, e.second - s.second};
	p tt = {ee.first - ss.first, ee.second - ss.second};
	return ccw({0, 0}, t, tt) >= 0;
}

ll f(ll t){ //ternary search
	for(int i=0; i<n; i++){
		arr[i] = {v[i].x + v[i].dx*t, v[i].y + v[i].dy*t};
	}
	swap(arr[0], *min_element(arr.begin(), arr.end()));
	sort(arr.begin()+1, arr.end(), [](p a, p b){
		int cw = ccw(arr[0], a, b);
		if(cw) return cw > 0;
		return dist(arr[0], a) < dist(arr[0], b);
	});

	//get convx hull
	vector<p> hull;
	for(int i=0; i<n; i++){
		while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), arr[i]) <= 0){
			hull.pop_back();
		}
		hull.push_back(arr[i]);
	}

	//rotating calipers
	ll ret = 0;
	int p = 0;

	for(int i=0; i<hull.size(); i++){
		while(p+1 < hull.size() && chk(hull[i], hull[i+1], hull[p], hull[p+1])){
			ret = max(ret, dist(hull[i], hull[p])); p++;
		}
		ret = max(ret, dist(hull[i], hull[p]));
	}

	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> t;
	v.resize(n), arr.resize(n);
	for(int i=0; i<n; i++) v[i].get();

	//ternary search
	ll s = 0, e = t;
	while(s+3 <= e){
		ll l = (s+s+e)/3, r = (s+e+e)/3;
		if(f(l) > f(r)) s = l;
		else e = r;
	}

	ll ans = 1e18;
	int idx = s;
	for(ll i=s; i<=e; i++){
		ll now = f(i);
		if(ans > now){
			ans = now;
			idx = i;
		}
	}
	cout << idx << "\n" << ans;
}

Compilation message (stderr)

dist.cpp: In function 'll f(ll)':
dist.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<hull.size(); i++){
               ~^~~~~~~~~~~~
dist.cpp:63:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p+1 < hull.size() && chk(hull[i], hull[i+1], hull[p], hull[p+1])){
         ~~~~^~~~~~~~~~~~~

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