oj.uz

Submission #154819

# Submission time Handle Problem Language Result Execution time Memory
154819 2019-09-25T01:44:31 Z aer0park None (KOI16_dist) C++14
2 / 100
 100 ms 2424 KB 
//code test : (not my code)
#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

dist.cpp: In function 'll f(ll)':
dist.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<hull.size(); i++){
               ~^~~~~~~~~~~~
dist.cpp:64: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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 12 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 12 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -