| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529409 |
2022-02-23T01:53:05 Z |
8e7 |
Fences (JOI18_fences) |
C++17 |
|
1 ms |
332 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define x first
#define y second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
pii vec(pii p, pii q) {return {q.x - p.x, q.y - p.y};}
ll dot(pii p, pii q){return p.x * q.x + p.y * q.y;}
ll cross(pii p, pii q){return p.x * q.y - p.y * q.x;}
int sgn(ll x){return (x > 0 ? 1 : (x == 0 ? 0 : -1));}
bool inl(pii p, pii l1, pii l2) {
return cross(vec(p, l1), vec(p, l2)) == 0 && dot(vec(p, l1), vec(p, l2)) <= 0;
}
bool inter(pii p1, pii p2, pii q1, pii q2) {
if (inl(p1, q1, q2) || inl(p2, q1, q2) || inl(q1, p1, p2) || inl(q2, p1, p2)) return 1;
if (sgn(cross(vec(p1, q1), vec(p1, q2))) != sgn(cross(vec(p2, q1), vec(p2, q2))) &&
sgn(cross(vec(q1, p1), vec(q1, p2))) != sgn(cross(vec(q2, p1), vec(q2, p2)))) return 1;
return 0;
}
ll sd(pii p, pii q){return (q.x - p.x) * (q.x - p.x) + (q.y - p.y) * (q.y - p.y);}
double getl(pii p){return sqrt(double(p.x * p.x + p.y * p.y));}
double dis(pii p, pii l1, pii l2) {
pii vi = vec(l1, l2);
if (sgn(dot(vi, vec(l1, p))) * sgn(dot(vi, vec(l2, p))) != 1) {
double len = dot(vec(l1, p), vi) / getl(vi);
return sqrt(double(sd(l1, p) - len * len));
} else {
ll mi = min(sd(p, l1), sd(p, l2));
return sqrt(double(mi));
}
}
double di[4];
int main() {
io
int n, s;
cin >> n >> s;
pii p1, p2;
cin >> p1.x >> p1.y >> p2.x >> p2.y;
pii q[4] = {{s, s}, {s, -s}, {-s, -s}, {-s, s}};
bool valid[4] = {0, 0, 0, 0};
double ans = 8 * s;
for (int i = 0;i < 4;i++) {
pii vl = vec(q[i], p1), vr = vec(q[i], p2);
pii wl = vec(q[(i+1)%4], q[(i+2)%4]), wr = vec(q[(i+1)%4], q[(i+2)%4]);
valid[i] = (!inter(q[i], p1,q[(i+1)%4], q[(i)%4]) &&
!inter(q[i], p1, q[(i+1)%4], q[(i+2)%4])) || (!inter(q[i], p2, q[(i+1)%4], q[(i)%4]) && !inter(q[i], p2, q[(i+1)%4], q[(i+2)%4]));
//debug(i, valid[i]);
di[i] = dis(q[i], p1, p2);
}
for (int i = 0;i < 4;i++) {
if (valid[i] && valid[(i+1)%4]) {
ans = min(ans, 6 * s + di[i] + di[(i+1)%4]);
}
if (valid[i] && valid[(i+2)%4]) {
ans = min(ans, 4 * s + di[i] + di[(i+2)%4]);
}
}
cout << fixed << setprecision(10) << ans << endl;
}
Compilation message
fences.cpp: In function 'int main()':
fences.cpp:58:7: warning: variable 'vl' set but not used [-Wunused-but-set-variable]
58 | pii vl = vec(q[i], p1), vr = vec(q[i], p2);
| ^~
fences.cpp:58:27: warning: variable 'vr' set but not used [-Wunused-but-set-variable]
58 | pii vl = vec(q[i], p1), vr = vec(q[i], p2);
| ^~
fences.cpp:59:7: warning: variable 'wl' set but not used [-Wunused-but-set-variable]
59 | pii wl = vec(q[(i+1)%4], q[(i+2)%4]), wr = vec(q[(i+1)%4], q[(i+2)%4]);
| ^~
fences.cpp:59:41: warning: variable 'wr' set but not used [-Wunused-but-set-variable]
59 | pii wl = vec(q[(i+1)%4], q[(i+2)%4]), wr = vec(q[(i+1)%4], q[(i+2)%4]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
312 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
312 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
312 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
