Submission #98852

#	Time	Username	Problem	Language	Result	Execution time	Memory
98852		jhnah917	먼 별 (KOI16_dist)	C++14	100 / 100	452 ms	3648 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){
	return ccw({0, 0}, {e.first-s.first, e.second-s.second}, {ee.first-ss.first, ee.second-ss.second}) >= 0;
}

ll f(int t){
	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(), [](const p a, const p b){
		int cw = ccw(arr[0], a, b);
		if(cw) return cw > 0;
		return dist(arr[0], a) < dist(arr[0], b);
	});
	
	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]);
	}
	
	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();
	ll s = 0, e = t;
	while(s+3 <= e){
		ll l = (s+s+e)/3, r = (s+e+e)/3;
		ll t1 = f(l), t2 = f(r);
		if(t1 > t2) 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(int)':
dist.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<hull.size(); i++){
               ~^~~~~~~~~~~~
dist.cpp:58: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