| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 153217 |
2019-09-13T00:54:38 Z |
gs18103 |
None (KOI16_dist) |
C++14 |
|
2000 ms |
2736 KB |
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
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] * (ll)t, arr[i][1] + arr[i][3] * (ll)t);
}
sort(all(p));
p.erase(unique(all(p)), p.end());
base = p[0];
sort(p.begin()+1, p.end(), [](pll a, pll b) {
return ccw(base, a, b) > 0;
});
ch.push_back(base);
for(int i = 1; i < p.size(); 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 idx = 0;
ll ret = 0;
for(int i = 0; i < ch.size(); i++) {
for(int j = 0; j < ch.size(); j++) {
ret = max(ret, dis(ch[i], ch[j]));
}
}
return ret;
}
int search(int s, int e) {
if(s + 10 >= e) {
ll dis = 9000000000000000000LL;
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:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < p.size(); i++) {
~~^~~~~~~~~~
dist.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ch.size(); i++) {
~~^~~~~~~~~~~
dist.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < ch.size(); j++) {
~~^~~~~~~~~~~
dist.cpp:43:6: warning: unused variable 'idx' [-Wunused-variable]
int idx = 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 |
380 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
296 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
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 |
380 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
296 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
16 ms |
376 KB |
Output is correct |
| 12 |
Correct |
36 ms |
376 KB |
Output is correct |
| 13 |
Correct |
13 ms |
376 KB |
Output is correct |
| 14 |
Correct |
16 ms |
376 KB |
Output is correct |
| 15 |
Incorrect |
10 ms |
376 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
149 ms |
2400 KB |
Output is correct |
| 3 |
Correct |
157 ms |
2388 KB |
Output is correct |
| 4 |
Execution timed out |
2049 ms |
2736 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
380 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
296 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
16 ms |
376 KB |
Output is correct |
| 12 |
Correct |
36 ms |
376 KB |
Output is correct |
| 13 |
Correct |
13 ms |
376 KB |
Output is correct |
| 14 |
Correct |
16 ms |
376 KB |
Output is correct |
| 15 |
Incorrect |
10 ms |
376 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
