QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386925#5112. Where Am I?Energy_is_not_over#WA 0ms4292kbC++173.3kb2024-04-11 21:36:382024-04-11 21:36:39

Judging History

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

  • [2024-04-11 21:36:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4292kb
  • [2024-04-11 21:36:38]
  • 提交

answer

//
// Stvoreno ENERGom o 11.04.24. 15:22:25
//

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define F first
#define fir first
#define S second
#define sec second
#define mp make_pair
#define MP make_pair
#define pb push_back
#define PB push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy
#define DEBUG for (int _____DEBUG=1;_____DEBUG;_____DEBUG=0)

template<class ...Ts>
auto &PRNT(Ts ...ts) { return ((cerr << ts << " "), ...); }

#define LOG(...) PRNT(#__VA_ARGS__" ::",__VA_ARGS__)<<endl
#else
#define DEBUG while (0)
#define LOG(...)
#endif

const int max_n = 111, inf = 1000111222;
const ld pi = 2 * acosl(0.0l);

struct Point {
    ld x, y;

    Point operator - (const Point &p) const {
        return {x - p.x, y - p.y};
    }

    Point operator + (const Point &p) const {
        return {x + p.x, y + p.y};
    }

    Point operator * (ld k) const {
        return {x * k, y * k};
    }

    Point rotate90ccw() const {
        return {-y, x};
    }

    ld len() const {
        return sqrtl(x * x + y * y);
    }
};

const ld eps = 1e-9;

int m, n;
vector<Point> poly[max_n];
ld from_z[max_n], to_z[max_n];
Point from[max_n], to[max_n];
bool ok[max_n];

ld vect_pr(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

bool is_inside(const vector<Point> &v, const Point &p) {
    for (int i = 0; i < v.size(); ++i) {
        if (vect_pr(v[i] - p, v[(i + 1) % v.size()] - v[i]) > eps) {
            return false;
        }
    }
    return true;
}

bool check(int ind, const vector<Point> &v) {
    for (const auto p : poly[ind]) {
        if (!is_inside(v, p)) {
            return false;
        }
    }
    return true;
}

bool check(ld ang) {
    memset(ok, 0, sizeof(ok));
    const ld coef = tanl(ang);
    for (int i = 0; i < m; ++i) {
        auto dir = (to[i] - from[i]).rotate90ccw();
        dir = dir * (1.0l / dir.len());
        const ld d1 = from_z[i] * coef;
        const ld d2 = to_z[i] * coef;
        vector<Point> v{
            from[i] + dir * d1,
            to[i] + dir * d2,
            to[i] - dir * d2,
            from[i] - dir * d1
        };
        for (int j = 0; j < n; ++j) {
            ok[j] |= check(j, v);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!ok[i])  {
            return false;
        }
    }
    return true;
}

int main() {
    freopen("input_f.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        poly[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> poly[i][j].x >> poly[i][j].y;
        }
    }
    for (int i = 0; i < m; ++i) {
        cin >> from[i].x >> from[i].y >> from_z[i] >> to[i].x >> to[i].y >> to_z[i];
    }
    ld l = eps, r = pi / 2 - eps;
    if (!check(r)) {
        cout << "impossible\n";
        return 0;
    }
    for (int it = 0; it < 74; ++it) {
        ld mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << fixed << setprecision(10) << r << "\n";
    exit(0);
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4292kb

input:

1 1
X

output:

0.0000000010

result:

wrong output format Unexpected end of file - int64 expected