QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386823#5103. Fair DivisionPetroTarnavskyi#RE 0ms0kbC++203.1kb2024-04-11 20:27:032024-04-11 20:27:04

Judging History

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

  • [2024-04-11 20:27:04]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-11 20:27:03]
  • 提交

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

output:


result: