Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define fixed(n) fixed << setprecision(n)
- #define ceil(n, m) (((n) + (m) - 1) / (m))
- #define add_mod(a, b, m) (((a % m) + (b % m)) % m)
- #define sub_mod(a, b, m) (((a % m) - (b % m) + m) % m)
- #define mul_mod(a, b, m) (((a % m) * (b % m)) % m)
- #define all(vec) vec.begin(), vec.end()
- #define rall(vec) vec.rbegin(), vec.rend()
- #define sz(x) int(x.size())
- #define debug(x) cout << #x << ": " << (x) << "\n";
- #define fi first
- #define se second
- #define ll long long
- #define ull unsigned long long
- #define EPS 1e-9
- constexpr int INF = 1 << 30, Mod = 1e9 + 7;
- constexpr ll LINF = 1LL << 62;
- #define PI acos(-1)
- template < typename T = int > using Pair = pair < T, T >;
- vector < string > RET = {"NO", "YES"};
- template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {
- for (auto &x : v) in >> x;
- return in;
- }
- template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) {
- for (const T &x : v) out << x << ' ';
- return out;
- }
- typedef complex < double > point;
- #define X real()
- #define Y imag()
- #define angle(a) (atan2((a).imag(), (a).real()))
- #define vec(a, b) ((b)-(a))
- #define same(p1, p2) (dp(vec(p1, p2), vec(p1,p2)) < EPS)
- #define dp(a, b) ( (conj(a) * (b)).real() ) // a * b cos(T), if zero -> prep
- #define cp(a, b) ( (conj(a) * (b)).imag() ) // a * b sin(T), if zero -> parllel
- #define length(a) (hypot((a).imag(), (a).real()))
- #define normalize(a) (a) / length(a)
- #define polar(r, ang) ((r) * exp(point(0, ang)))
- #define rotateO(p, ang) ((p) * exp(point(0, ang)))
- #define rotateA(p, ang, about) (rotateO(vec(about, p), ang) + about)
- int dcmp(double a, double b) { return fabs(a - b) <= EPS ? 0 : a < b ? -1 : 1; }
- istream& operator >> (istream &in, point& p) {
- double x, y;
- in >> x >> y;
- p = point(x, y);
- return in;
- }
- ostream& operator << (ostream &out, const point& p) {
- out << p.X << ' ' << p.Y;
- return out;
- }
- double dist(point& a, point& b) {
- return hypot(a.X - b.X, a.Y - b.Y);
- }
- double TriangleArea(point& a, point& b, point& c) {
- return fabs(cp(b - a, c - a)) / 2.0;
- }
- void Solve(){
- int n;
- cin >> n;
- point S;
- cin >> S;
- deque < point > P(n);
- for(auto& p : P)
- cin >> p;
- sort(all(P), [&](point& a, point& b) {
- return dist(S, a) < dist(S, b);
- });
- double MaxArea = 0;
- vector < int > next(n, -1), nextnext(n, -1);
- for(int i = 0; i < n; i++){
- for(int j = 0; j < n; j++){
- if(i == j) continue;
- double distA = dist(P[i], P[j]);
- if(next[i] == -1)
- next[i] = j;
- else if(distA < dist(P[i], P[next[i]]))
- nextnext[i] = next[i], next[i] = j;
- else if(nextnext[i] == -1 || distA < dist(P[i], P[nextnext[i]]))
- nextnext[i] = j;
- }
- }
- vector < bool > is_removed(n, false);
- for(int i = 0; i < n; i++){
- is_removed[i] = true;
- double MinArea = 1e18;
- for(int j = 0; j < n; j++){
- if(i == j) continue;
- if(!is_removed[next[j]])
- MinArea = min(MinArea, TriangleArea(S, P[j], P[next[j]]));
- else
- MinArea = min(MinArea, TriangleArea(S, P[j], P[nextnext[j]]));
- }
- MaxArea = max(MaxArea, MinArea);
- is_removed[i] = false;
- }
- cout << fixed(10) << MaxArea << '\n';
- }
- int main(){
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- int test_cases = 1;
- // cin >> test_cases;
- for(int tc = 1; tc <= test_cases; tc++){
- // cout << "Case #" << tc << ": ";
- Solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement