QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354756 | #5104. Guardians of the Gallery | JerryTcl | WA | 1ms | 3996kb | C++20 | 6.2kb | 2024-03-15 23:42:23 | 2024-03-15 23:42:24 |
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 double Len(cVec a) { return sqrt(Len2(a)); }
inline istream &operator >> (istream &in, Pnt &p) { return in >> p.x >> p.y; }
inline ostream &operator << (ostream &ou, Pnt &p) { return ou << 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 != p && C != q && In(C, p, q)) 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;
double fl = 0, fr = 1; const double len = Len(v - u);
const auto maintain = [&](cPnt p, cPnt q) {
const auto &calc = [&](cPnt p) { return Len(p - u) / len; };
double x = calc(p), y = calc(q); if(x > y) ::swap(x, y);
if(dCmp(x, fl) != 1) fl = max(fl, y); else fr = min(fr, x);
};
for(int i = 0; i < (int)size(); ++i) {
cPnt p = (*this)[i], z = (*this)[nxtp(i)];
if(In(p, u, v) || !In(z, u, v)) continue;
for(int j = nxtp(i);; j = nxtp(j)) {
cPnt q = (*this)[nxtp(j)]; if(In(q, u, v)) continue;
const int x = dSgn(Cro(p - u, v - u));
const int y = dSgn(Cro(q - u, v - u)); if(x == -y) return !x;
maintain(x ? z : p, y ? (*this)[j] : q); break;
}
}
const double f = (fl + fr) * .5;
cPnt m = u * (1 - f) + v * f; int result = 0;
for(int i = 0; i < (int)size(); ++i) {
cPnt p = (*this)[i], q = (*this)[nxtp(i)];
if(p.y < q.y && dIn<0>(m.y, p.y, q.y))
result += dSgn(Cro(q - p, m - p)) == 1;
if(p.y > q.y && dIn<0>(m.y, q.y, p.y))
result += dSgn(Cro(p - q, m - q)) == 1;
}
return result & 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 len = Len(OP), len2 = Len2(OP);
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 = Len(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);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
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: 3820kb
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: 0ms
memory: 3996kb
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: 0
Accepted
time: 1ms
memory: 3988kb
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:
64.2045377025227
result:
ok found '64.2045377', expected '64.2045377', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3996kb
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 33 23 81 12
output:
1000000000000000000.0000000000000
result:
wrong answer 1st numbers differ - expected: '72.2834980', found: '1000000000000000000.0000000', error = '13834416251276884.0000000'