QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#386823 | #5103. Fair Division | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 3.1kb | 2024-04-11 20:27:03 | 2024-04-11 20:27:04 |
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const db EPS = 1e-9;
const db INF = 1e47;
const db PI = acos(-1.0);
template<typename T>
void updMin(T& a, T b)
{
a = min(a, b);
}
template<typename T>
void updMax(T& a, T b)
{
a = max(a, b);
}
struct Pt
{
db x, y;
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.x};
}
Pt operator*(db d) const
{
return {x * d, y * d};
}
Pt operator/(db d) const
{
return {x / d, y / d};
}
};
db sq(const Pt& p)
{
return p.x * p.x + p.y * p.y;
}
db abs(const Pt& p)
{
return sqrt(sq(p));
}
int sgn(db x)
{
return (EPS < x) - (x < -EPS);
}
Pt perp(const Pt& p)
{
return {-p.y, p.x};
}
db dot(const Pt& p, const Pt& q)
{
return p.x * q.x + p.y * q.y;
}
db cross(const Pt& p, const Pt& q)
{
return p.x * q.y - p.y * q.x;
}
db orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p) / abs(q - p);
}
struct Line
{
Pt n;
db c;
Line (const Pt& p, const Pt& q):
n(perp(q - p)), c(-dot(n, p)) {}
db side(const Pt& p) const
{
return dot(n, p) + c;
}
db dist(const Pt& p) const
{
return abs(side(p)) / abs(n);
}
bool cmpProj(const Pt& p, const Pt& q) const
{
return sgn(cross(p, n) - cross(q, n)) < 0;
}
Pt proj(const Pt& p) const
{
return p - n * side(p) / sq(n);
}
};
pair<db, bool> segPt(const Pt& a, const Pt& b, const Pt& p)
{
Line l(a, b);
assert(sgn(sq(l.n)) != 0);
if (l.cmpProj(a, p) && l.cmpProj(p, b))
return {l.dist(p), true};
return {0, false};
}
struct Flight
{
Pt p1, p2;
db z1, z2;
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int n, m;
cin >> n >> m;
vector<vector<Pt>> islands(n);
for (auto& island : islands)
{
int k;
cin >> k;
island.resize(k);
for (Pt& p : island)
cin >> p.x >> p.y;
}
vector<Flight> flights(m);
for (auto& flight : flights)
cin >> flight.p1.x >> flight.p1.y >> flight.z2 >> flight.p2.x >> flight.p2.y >> flight.z2;
db ans = 0;
for (const auto& island : islands)
{
db ansIsland = INF;
for (const auto& flight : flights)
{
db ansIslandFlight = 0;
bool canCover = true;
Line l(flight.p1, flight.p2);
for (const Pt& p : island)
{
auto [d, ok] = segPt(flight.p1, flight.p2, p);
canCover &= ok;
if (!canCover)
break;
Pt q = l.proj(p);
db z = (flight.z2 - flight.z1) * (abs(q - flight.p1) / abs(flight.p2 - flight.p1)) + flight.z1;
updMax(ansIslandFlight, d / z);
}
if (canCover)
{
updMin(ansIsland, ansIslandFlight);
}
}
updMax(ans, ansIsland);
}
if (ans > 1e40)
{
cout << "impossible\n";
return 0;
}
cout << atan(ans) * 180 / PI << "\n";
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
13 382475111752106101