oj.uz

Submission #153196

# Submission time Handle Problem Language Result Execution time Memory
153196 2019-09-12T21:04:51 Z gs18103 None (KOI16_dist) C++14
2 / 100
 212 ms 2792 KB 
#include <bits/stdc++.h>
#define x first
#define y second
 
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
 
ll arr[30303][4];
pll base;
int n, T;

ll ccw(pll a, pll b, pll c) {
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

ll dis(pll a, pll b) {
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

ll cal_dis(int t) {
	vector <pll> p, ch;
	for(int i = 0; i < n; i++) {
		p.emplace_back(arr[i][0] + arr[i][2] * t, arr[i][1] + arr[i][3] * t);
	}
	sort(p.begin(), p.end());
	base = p[0];
	sort(p.begin()+1, p.end(), [](pll a, pll b) {
		if(ccw(base, a, b) == 0) return dis(base, a) < dis(base, b);
		return ccw(base, a, b) > 0;
	});
	ch.push_back(base);
	for(int i = 1; i < n; i++) {
		while(ch.size() >= 2) {
			pll p1 = ch[ch.size()-2], p2 = ch[ch.size()-1];
			if(ccw(p1, p2, p[i]) > 0) break;
			ch.pop_back();
		}
		ch.push_back(p[i]);
	}

	int d1 = 0, d2 = 0;
	ll ret = 0, pre = -1;
	while(d1 < ch.size() && d2 < ch.size()) {
		ll d = dis(ch[d1], ch[d2]);
		if(d > pre) pre = d, d2++;
		else d2--, d1++, pre = -1;
		ret = max(ret, pre);
	}
	return ret;
}

int search(int s, int e) {
	if(s + 10 >= e) 	{
		ll dis = 7000000000000000000LL;
		for(int i = s; i <= e; i++) {
			dis = min(dis, cal_dis(i));
		}
		for(int i = s; i <= e; i++) {
			if(dis == cal_dis(i)) return i;
		}
	}
	int t1 = (2 * s + e) / 3, t2 = (s + 2 * e) / 3;
	ll dis1 = cal_dis(t1), dis2 = cal_dis(t2);
	if(dis1 <= dis2) return search(s, t2);
	else return search(t1, e);
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> T;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 4; j++) {
			cin >> arr[i][j];
		}
	}
	int ans = search(0, T);
	cout << ans << '\n' << cal_dis(ans);
}

Compilation message

dist.cpp: In function 'll cal_dis(int)':
dist.cpp:44:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(d1 < ch.size() && d2 < ch.size()) {
        ~~~^~~~~~~~~~~
dist.cpp:44:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(d1 < ch.size() && d2 < ch.size()) {
                          ~~~^~~~~~~~~~~

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 256 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 2 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 256 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 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 17 ms 480 KB Output is correct
12 Incorrect 16 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 2440 KB Output is correct
2 Correct 158 ms 2480 KB Output is correct
3 Correct 168 ms 2336 KB Output is correct
4 Incorrect 113 ms 2792 KB Output isn't correct
5 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 256 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 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 17 ms 480 KB Output is correct
12 Incorrect 16 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -