| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529085 |
2022-02-22T05:54:10 Z |
fhvirus |
Fences (JOI18_fences) |
C++17 |
|
1 ms |
320 KB |
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif
const double eps = 1e-7;
struct Vec {
double x, y;
Vec(double _x = 0, double _y = 0): x(_x), y(_y) {}
const Vec operator + (const Vec& o) const { return Vec(x + o.x, y + o.y); }
const Vec operator - (const Vec& o) const { return Vec(x - o.x, y - o.y); }
const Vec operator * (const double& m) const { return Vec(x * m, y * m); }
const bool operator != (const Vec& o) const { return fabs(x - o.x) > eps or fabs(y - o.y) > eps; }
const Vec T() const { return Vec(y, -x); }
};
struct Seg {
Vec a, b;
Seg() = default;
Seg(Vec _a, Vec _b): a(_a), b(_b) {}
Seg(double _a, double _b, double _c, double _d): a(_a, _b), b(_c, _d) {}
const Vec getVec() const { return Vec(b.x - a.x, b.y - a.y); }
};
double dot(const Vec& a, const Vec& b)
{ return a.x * b.x + a.y * b.y; }
double cross(const Vec& a, const Vec& b)
{ return a.x * b.y - a.y * b.x; }
double abs2(const Vec& a)
{ return a.x * a.x + a.y * a.y; }
double abs(const Vec& a)
{ return sqrt(a.x * a.x + a.y * a.y); }
double getDist(const Vec& a, const Vec& b)
{ return sqrt(abs2(b - a)); }
double getLen(const Seg& s)
{ return sqrt(abs2(s.getVec())); }
bool getHalf(const Vec& a)
{ return a.y > eps or (fabs(a.y) <= eps and a.x > eps); }
int sgn(double a) { return (a > eps) - (a < -eps); }
bool on(const Vec& v, const Seg& s) {
Vec a = s.a - v;
Vec b = s.b - v;
debug(a.x, a.y, b.x, b.y, sgn(cross(a, b)), sgn(dot(a, b)));
return sgn(cross(a, b)) == 0 and sgn(dot(a, b)) < 0;
}
bool intersect(const Seg& a, const Seg& b) {
int c123 = sgn(cross(a.b - a.a, b.a - a.a));
int c124 = sgn(cross(a.b - a.a, b.b - a.a));
int c341 = sgn(cross(b.b - b.a, a.a - b.a));
int c342 = sgn(cross(b.b - b.a, a.b - b.a));
return (c123 * c124 < 0 and c341 * c342 < 0);
}
const int kN = 101;
const int kP = kN * 3;
int N, S;
Seg segs[kN], edge[4];
Vec pts[kP];
const double INF = 1e18;
bool crossed_pasture(Seg s) {
for (int i = 0; i < 4; ++i)
if (intersect(s, Seg(pts[i], pts[(i + 1) % 4]))) return true;
if (intersect(s, Seg(S, 0, -S, 0))) return true;
if (intersect(s, Seg(0, S, 0, -S))) return true;
return on(Vec(0, 0), s);
}
bool has_T(Vec v, Seg s) {
Vec a = s.a - v;
Vec b = s.b - v;
return fabs(cross(a, b) <= eps) and sgn(dot(a, b)) < 0;
}
double to(Vec a, Vec b) {
Seg s(a, b);
double len = crossed_pasture(s) ? INF : abs(b - a);
debug(a.x, a.y, b.x, b.y, len);
return len;
}
double to(int p, Seg s) {
double len = INF;
Vec v = pts[p];
len = min(len, to(pts[p], s.a));
len = min(len, to(pts[p], s.b));
if (has_T(v, s)) {
Vec to_T = s.getVec().T();
to_T = to_T * (cross(s.b - v, s.a - v) / abs2(s.getVec()));
if (!crossed_pasture(Seg(pts[p], pts[p] + to_T)))
len = min(len, abs(to_T));
}
return len;
}
double go(int a, int b, Seg seg) {
return to(a, seg) + to(b, seg);
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> S;
Seg seg;
{
int a, b, c, d;
cin >> a >> b >> c >> d;
seg = Seg(a, b, c, d);
}
pts[0] = Vec( S, S);
pts[1] = Vec( S,-S);
pts[2] = Vec(-S,-S);
pts[3] = Vec(-S, S);
double ans = 8 * S;
ans = min(ans, go(0, 1, seg) + 6 * S);
debug(ans);
ans = min(ans, go(1, 2, seg) + 6 * S);
debug(ans);
ans = min(ans, go(2, 3, seg) + 6 * S);
debug(ans);
ans = min(ans, go(3, 0, seg) + 6 * S);
debug(ans);
ans = min(ans, go(0, 2, seg) + 4 * S);
debug(ans);
ans = min(ans, go(1, 3, seg) + 4 * S);
debug(ans);
cout << setprecision(12) << fixed << ans << '\n';
return 0;
}
Compilation message
fences.cpp: In function 'bool on(const Vec&, const Seg&)':
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:53:2: note: in expansion of macro 'debug'
53 | debug(a.x, a.y, b.x, b.y, sgn(cross(a, b)), sgn(dot(a, b)));
| ^~~~~
fences.cpp: In function 'double to(Vec, Vec)':
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:87:2: note: in expansion of macro 'debug'
87 | debug(a.x, a.y, b.x, b.y, len);
| ^~~~~
fences.cpp: In function 'int main()':
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:126:2: note: in expansion of macro 'debug'
126 | debug(ans);
| ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:128:2: note: in expansion of macro 'debug'
128 | debug(ans);
| ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:130:2: note: in expansion of macro 'debug'
130 | debug(ans);
| ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:132:2: note: in expansion of macro 'debug'
132 | debug(ans);
| ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:134:2: note: in expansion of macro 'debug'
134 | debug(ans);
| ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
fences.cpp:136:2: note: in expansion of macro 'debug'
136 | debug(ans);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
320 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
320 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
320 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
