QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#386925 | #5112. Where Am I? | Energy_is_not_over# | WA | 0ms | 4292kb | C++17 | 3.3kb | 2024-04-11 21:36:38 | 2024-04-11 21:36:39 |
Judging History
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