| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 197014 |
2020-01-18T06:20:33 Z |
dennisstar |
None (KOI16_dist) |
C++11 |
|
68 ms |
2380 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
#define fastio ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
int N, T;
ll x[30010], y[30010], dx[30010], dy[30010];
pll operator -(pll p1, pll p2) { return pll(p1.fi-p2.fi, p1.se-p2.se); }
int ccw(pll v1, pll v2) {
if (v1.fi*v2.se-v1.se*v2.fi > 0) return 1; //ccw
else if (v1.fi*v2.se-v1.se*v2.fi < 0) return -1; //cw
else return 0; //collinear
}
int ccw1(pll p1, pll p2, pll p3) { return ccw(p2-p1, p3-p1); }
int ccw2(pll p1, pll p2, pll p3, pll p4) { return ccw(p2-p1, p4-p3); }
ll sq(int k) { return k*k; }
vector<pll> make_ch(vector<pll> &P) { //convex hull
sort(all(P)); unq(P);
vector<pll> ch;
for (auto &i:P) {
while (ch.size()>1 && ccw1(ch[ch.size()-2], ch.back(), i)!=1) ch.pop_back();
ch.eb(i);
}
reverse(all(P)); int tp=ch.size();
for (auto &i:P) {
while (tp<ch.size() && ccw1(ch[ch.size()-2], ch.back(), i)!=1) ch.pop_back();
ch.eb(i);
}
ch.pop_back();
return ch;
}
ll dist(vector<pll> &P) {
P=make_ch(P); ll ret=0;
for (int i=0, j=1; i<P.size(); i++) {
while (ccw2(P[i], P[(i+1)%P.size()], P[j], P[(j+1)%P.size()])==1) j=(j+1)%P.size();
ret=max(ret, sq(P[i].fi-P[j].fi)+sq(P[i].se-P[j].se));
}
return ret;
}
ll solve(int t) {
vector<pll> P;
for (int i=1; i<=N; i++) P.eb(x[i]+dx[i]*t, y[i]+dy[i]*t);
return dist(P);
}
int main() {
scanf("%d %d", &N, &T);
for (int i=1; i<=N; i++) scanf("%lld %lld %lld %lld", &x[i], &y[i], &dx[i], &dy[i]);
vector<pll> p;
int s=0, e=T, mi=0;
while (s<e-3) {
int m1=(s*2+e)/3, m2=(s+e*2)/3;
ll r1=solve(m1), r2=solve(m2);
if (r1>r2) s=m1;
else if (r1<r2) e=m2;
else s=m1, e=m2;
}
pll ans=pll((1ll<<60), (1ll<<60));
for (int i=s; i<=e; i++) ans=min(ans, pll(solve(i), (ll)i));
printf("%lld\n%lld\n", ans.se, ans.fi);
return 0;
}
Compilation message
dist.cpp: In function 'std::vector<std::pair<long long int, long long int> > make_ch(std::vector<std::pair<long long int, long long int> >&)':
dist.cpp:39:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (tp<ch.size() && ccw1(ch[ch.size()-2], ch.back(), i)!=1) ch.pop_back();
~~^~~~~~~~~~
dist.cpp: In function 'll dist(std::vector<std::pair<long long int, long long int> >&)':
dist.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0, j=1; i<P.size(); i++) {
~^~~~~~~~~
dist.cpp: In function 'int main()':
dist.cpp:65:16: warning: unused variable 'mi' [-Wunused-variable]
int s=0, e=T, mi=0;
^~
dist.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &T);
~~~~~^~~~~~~~~~~~~~~~~
dist.cpp:63:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=N; i++) scanf("%lld %lld %lld %lld", &x[i], &y[i], &dx[i], &dy[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
2380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
