QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354659 | #5104. Guardians of the Gallery | JerryTcl | WA | 1ms | 4092kb | C++20 | 5.2kb | 2024-03-15 20:36:36 | 2024-03-15 20:36:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
template<typename T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using MaxHeap = priority_queue<T, vector<T>, less<T>>;
constexpr double eps = 1e-9;
int dSgn(double x) { return x < -eps ? -1 : x > eps ? 1 : 0; }
int dCmp(double x, double y) { return dSgn(x - y); }
template<int CloseR = 1, int CloseL = 1> int dIn(double x, double l, double r)
{ return (CloseL ? l - eps : l + eps) < x && x < (CloseR ? r + eps : r - eps); }
typedef struct Pnt { double x, y; } Vec;
using cPnt = const Pnt; using cVec = const Vec;
inline Vec operator + (cVec a, cVec b) { return {a.x + b.x, a.y + b.y}; }
inline Vec operator - (cVec a, cVec b) { return {a.x - b.x, a.y - b.y}; }
inline Vec operator * (cVec a, const double b) { return {a.x * b, a.y * b}; }
inline Vec operator / (cVec a, const double b) { return {a.x / b, a.y / b}; }
inline int operator == (cPnt a, cPnt b) { return !dCmp(a.x, b.x) && !dCmp(a.y, b.y); }
inline int operator != (cPnt a, cPnt b) { return dCmp(a.x, b.x) || dCmp(a.y, b.y); }
inline double Dot(cVec a, cVec b) { return a.x * b.x + a.y * b.y; }
inline double Cro(cVec a, cVec b) { return a.x * b.y - a.y * b.x; }
inline double Len2(cVec a) { return Dot(a, a); }
inline istream &operator >> (istream &in, Pnt &p) { return in >> p.x >> p.y; }
inline int In(cPnt p, cPnt a, cPnt b) {
cVec PA = a - p, PB = b - p;
return !dSgn(Cro(PA, PB)) && dSgn(Dot(PA, PB)) <= 0;
}
struct Polygon : vector<Pnt> {
Polygon(int n) : vector<Pnt>(n) {}
int nxtp(int x) const { return x + 1 == (int)size() ? 0 : x + 1; }
void getXs(vector<Pnt> &ret, cPnt u, cPnt v) const {
for(int i = 0; i < (int)size(); ++i) {
cPnt p = (*this)[i], q = (*this)[nxtp(i)];
cVec UV = v - u, PU = u - p, PV = v - p, PQ = q - p;
if(!dSgn(Cro(UV, PQ))) continue;
const double area0 = Cro(PU, PQ), area1 = Cro(PV, PQ);
cPnt C = u + UV * (area0 / (area0 - area1));
if(C == q) ++i; else if(C != p && In(C, q, p)) ret.push_back(C);
}
}
int containLine(cPnt u, cPnt v) const {
static vector<Pnt> buf; buf.clear(), getXs(buf, u, v);
for(cPnt p : buf) if(In(p, u, v)) return 0;
cPnt mid = (u + v) * .5; int ret = 0;
for(int i = 0; i < (int)size(); ++i) {
cPnt p = (*this)[i], q = (*this)[nxtp(i)];
if(In(mid, p, q)) return 1; if(p.y == q.y) continue;
if(p.y < q.y && dIn<0>(mid.y, p.y, q.y))
ret += dSgn(Cro(q - p, mid - p)) == 1;
if(p.y > q.y && dIn<0>(mid.y, q.y, p.y))
ret += dSgn(Cro(p - q, mid - q)) == 1;
}
return ret & 1;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n; Polygon pg(n); Pnt goal;
for(int i = 0; i < n; ++i) cin >> pg[i];
vector<pair<Pnt, double>> keys(n + 1);
cin >> keys[0].fi >> goal, keys[0].se = 1e18;
for(int i = 1; i <= n; ++i) keys[i] = {pg[i - 1], 1e18};
const auto &check = [&](cPnt x) {
int l = 0, r = 0;
for(int i = 0; i < (int)pg.size(); ++i) {
cPnt p = pg[i], q = pg[pg.nxtp(i)];
if(In(p, x, goal) && x != p) {
const int w = dSgn(Cro(x - goal, q - goal));
if(w) { w == 1 ? ++l : ++r; if(l && r) return 0; }
}
if(In(q, x, goal) && x != q) {
const int w = dSgn(Cro(x - goal, p - goal));
if(w) { w == 1 ? ++l : ++r; if(l && r) return 0; }
}
}
return 1;
};
const auto &checkpnt = [&](cPnt p) {
return pg.containLine(p, goal) && check(p); };
for(int i = 0; i <= n; ++i) if(checkpnt(keys[i].fi)) {
static vector<Pnt> buf; keys[i].se = 0;
buf.clear(), pg.getXs(buf, keys[i].fi, goal);
pair<double, int> mn = {1e18, -1};
for(int j = 0; j < (int)buf.size(); ++j) {
double l = buf[j].x, r = goal.x; if(l > r) swap(l, r);
if(dIn(keys[i].fi.x, l, r)) mn = \
min(mn, {Len2(keys[i].fi - buf[j]), j});
}
if(mn.se != -1 && check(buf[mn.se])) keys.emplace_back(buf[mn.se], 0);
}
const int z = (int)keys.size();
for(int i = 0; i < z; ++i) if(keys[i].se == 0) {
cPnt P = keys[i].fi; cVec OP = P - goal;
const double len2 = Len2(OP), len = sqrt(len2);
for(int j = 0; j < z; ++j) {
cPnt Q = keys[j].fi; cVec OQ = Q - goal;
const double fr = Dot(OP, OQ) / len2;
if(!dIn(fr, 0, 1)) continue;
if(pg.containLine(Q, goal + OP * fr))
keys[j].se = min(keys[j].se, abs(Cro(OP, OQ)) / len);
}
}
MinHeap<pair<double, int>> Q;
for(int i = 0; i < z; ++i) Q.emplace(keys[i].se, i);
while(!Q.empty() && Q.top().se) {
const auto [d, u] = Q.top(); Q.pop();
if(keys[u].se != d) continue;
for(int v = 0; v < z; ++v) {
const double len = sqrt(Len2(keys[u].fi - keys[v].fi));
if(d + len < keys[v].se && pg.containLine( \
keys[u].fi, keys[v].fi)) Q.emplace(keys[v].se = d + len, v);
}
}
printf("%.13lf", keys[0].se);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3824kb
input:
15 13 7 20 20 39 20 49 7 73 13 100 5 117 38 98 20 80 20 66 40 68 20 51 20 41 39 22 48 2 39 10 20 104 20
output:
29.0000000000000
result:
ok found '29.0000000', expected '29.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
16 39 2 48 22 39 41 20 51 20 68 40 66 20 80 20 98 38 117 5 100 13 73 7 49 19 39 20 23 20 20 7 13 20 10 20 104
output:
13.0000000000000
result:
ok found '13.0000000', expected '13.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4092kb
input:
16 13 33 20 60 23 66 39 97 49 105 73 166 100 205 117 272 98 216 80 180 66 172 68 156 51 122 41 121 22 92 2 44 10 40 104 228
output:
140.8722825824867
result:
ok found '140.8722826', expected '140.8722826', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 4024kb
input:
16 64 17 50 28 67 23 65 18 77 4 88 20 78 10 70 29 61 28 47 32 54 17 43 13 35 20 41 30 27 20 42 6 81 12 33 23
output:
60.2776755407364
result:
wrong answer 1st numbers differ - expected: '64.2045377', found: '60.2776755', error = '0.0611618'