QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353611#5106. Islands from the SkyJerryTclWA 1ms4224kbC++201.9kb2024-03-14 12:47:532024-03-14 12:47:54

Judging History

你现在查看的是最新测评结果

  • [2024-03-14 12:47:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4224kb
  • [2024-03-14 12:47:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9, INV_DEG = 180 / acos(-1);
typedef struct Pnt { double x, y; } Vec; using cPnt = const Pnt;
struct Pnt3D { Pnt p; double h; }; using cPnt3D = const Pnt3D;
inline istream &operator >> (istream &in, Pnt &p) { return in >> p.x >> p.y; }
inline istream &operator >> (istream &in, Pnt3D &p) { return in >> p.p >> p.h; }
inline Vec operator + (const Vec a, const Vec b) { return {a.x + b.x, a.y + b.y}; }
inline Vec operator - (const Vec a, const Vec b) { return {a.x - b.x, a.y - b.y}; }
inline double Dot(const Vec a, const Vec b) { return a.x * b.x + a.y * b.y; }
inline double Cro(const Vec a, const Vec b) { return a.x * b.y - a.y * b.x; }
inline double Len(const Vec a) { return sqrt(Dot(a, a)); }
auto Calc(cPnt p, cPnt3D &a, cPnt3D &b) -> pair<int, double> {
    const Vec AP = p - a.p, BP = p - b.p, AB = b.p - a.p;
    const double len = Len(AB), proj = Dot(AP, AB) / len;
    if(proj < -eps || proj > len + eps) return {1, 0};
    return {0, abs(Cro(AP, BP)) / ((len - proj) * a.h + proj * b.h)};
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<vector<Pnt>> polygons(n);
    for(int i = 0, s; i < n; ++i) {
        cin >> s, polygons[i].resize(s);
        for(Pnt &p : polygons[i]) cin >> p;
    }
    vector<array<Pnt3D, 2>> airlines(m);
    pair<int, double> ans = {0, 0};
    for(auto &[x, y] : airlines) cin >> x >> y;
    for(int i = 0; i < n; ++i) {
        const auto &g = polygons[i];
        const int s = g.size() - 1;
        pair<int, double> mincost = {1, 0};
        for(const auto &[x, y] : airlines) {
            pair<int, double> mx = {0, 0};
            for(int i = 0; i < s; ++i)
                mx = max(mx, Calc(g[i], x, y));
            mincost = min(mincost, mx);
        }
        ans = max(ans, mincost);
    }
    if(ans.first == 1) puts("impossible");
    else printf("%.9lf", INV_DEG * atan(ans.second));
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4224kb

input:

1 1
3
-5 0
5 0
0 5
-10 10 10 10 10 10

output:

45.000000000

result:

ok 

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 4140kb

input:

1 1
3
-5 0
5 0
0 5
-10 0 10 10 0 10

output:

0.000000000

result:

wrong answer