Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⢛⣉⣥⣤⣶⣶⣶⣶⣶⣶⣤⣬⣉⡛⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⣩⣴⣾⣿⣿⣿⣿⣿⣿⡿⠟⠛⠛⠻⢿⣿⣿⣷⣦⣍⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⣡⣾⣿⣿⣿⣿⣿⣿⣿⡿⢃⣴⣾⣿⠋⣁⣀⠙⣿⣿⣿⣿⣷⣌⠹⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢡⣾⣿⣿⣿⣿⣿⣿⣿⣿⡿⠇⣼⣿⣿⣿⣷⠸⣿⣿⣿⣿⣿⣿⣿⣿⣷⣌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣰⣿⣿⣿⣿⣿⣿⣿⡿⡋⢑⣤⣤⡙⢿⣿⡿⠟⣠⣈⠝⠻⣿⣿⣿⣿⣿⣿⣿⣆⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⡟⢰⣿⣿⣿⣿⣿⣿⡿⡃⣠⣾⣿⣿⣿⣷⣶⣶⣶⣾⣿⣿⣷⣄⢈⢿⣿⣿⣿⣿⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⠃⣿⣿⣿⣿⣿⣿⡟⠀⣴⣿⣿⣿⣿⡿⠟⠛⠛⠻⢿⣿⣿⣿⣿⣧⠉⢻⣿⣿⣿⣿⣿⣿⡈⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⡿⢸⣿⣿⣿⣿⣿⣿⢣⢰⣿⣿⣿⣿⠏⣠⣾⣿⣿⣷⣦⠹⣿⣿⣿⣿⡇⡌⣿⣿⣿⣿⣿⣿⡇⢻⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿⣿⣿⢿⣿⣿⠸⢸⣿⣿⣿⣿⠀⣿⣿⣿⣿⣿⣿⠄⣿⣿⣿⣿⡇⠀⣿⣿⣿⣿⣿⣿⡇⢸⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⡇⡀⣿⠋⣤⣤⣤⡙⢿⣿⣆⠹⣿⣿⣿⣿⠟⣰⣿⣿⠟⠛⠃⠢⣿⣿⣿⣿⣿⣿⡇⣾⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⡈⣿⣿⡇⢳⣤⣼⣿⣿⣿⣿⢘⣿⣿⣷⣦⣬⣤⣴⣾⣿⡿⢡⣾⣿⣿⣷⡌⢻⣿⣿⣿⣿⢁⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⢧⠸⣿⣿⣄⠻⠿⣿⣿⠿⠋⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣿⣿⣿⣿⠘⣿⣿⣿⠏⣼⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠹⣿⣿⣿⣶⣶⣶⣶⣦⣄⡉⣛⠿⠿⠿⠿⠿⠿⠛⠉⣂⣤⣉⡉⢹⠟⣰⣿⣿⠏⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⡘⢿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣭⣥⣤⣤⣴⣶⣿⣿⡿⠋⢀⣡⣴⣿⡿⢋⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣆⡙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣉⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⣋⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣬⣉⡛⠻⠿⠿⠿⠿⠿⠿⠟⢛⣋⣥⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣶⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
- */
- #pragma GCC optimize("Ofast")
- #pragma GCC target("avx2")
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <list>
- #include <unordered_map>
- #include <unordered_set>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef string str;
- //typedef __int128 ultraint;
- #define endl "\n"
- #define sqrt sqrtl
- //#define pow fast_pow
- const ll inf = (ll)1e18 + 7;
- ld eps = 1e-6;
- struct Point {
- ld x, y;
- };
- ld getl(Point a, Point b) {
- return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
- }
- ld getS(Point a, Point b, Point c) {
- ld ab = getl(a, b);
- ld bc = getl(b, c);
- ld ac = getl(a, c);
- ld p = (ab + bc + ac) / 2.0;
- return sqrt(p * (p - ab) * (p - bc) * (p - ac));
- }
- ld getSmn(vector <Point> &path) {
- ld ans = 0;
- ll i, n = path.size();
- for (i = 0; i < n; i++) {
- ans += (path[i].x * path[(i + 1) % n].y) - (path[(i + 1) % n].x * path[i].y);
- }
- return fabs(ans) / 2.0;
- }
- struct pr {
- ld a, b, c;
- };
- pr ur_pr(Point A, Point B) {
- ld a, b, c;
- a = B.y - A.y;
- b = A.x - B.x;
- c = (-1) * (a * A.x + b * A.y);
- return { a,b,c };
- }
- Point base{ inf,inf };
- bool cmp(Point a, Point b) {
- ll ans = (a.x - base.x) * (b.y - base.y) - (b.x - base.x) * (a.y - base.y);
- if (ans == 0) {
- return getl(base, a) < getl(base, b);
- }
- else {
- return ans > 0;
- }
- }
- ld check(ld m, vector <Point>& a) {
- ll i, n = a.size();
- vector <Point> path1, path2;
- for (i = 0; i < n; i++) {
- if (a[i].x <= m) {
- if (i > 0 && a[i - 1].x > m) {
- pr sup = ur_pr(a[i], a[i - 1]);
- ld y = (-sup.a * m - sup.c) / sup.b;
- path1.push_back({ m,y });
- path2.push_back({ m,y });
- }
- path1.push_back(a[i]);
- }
- else {
- if (i > 0 && a[i - 1].x <= m) {
- pr sup = ur_pr(a[i], a[i - 1]);
- ld y = (-sup.a * m - sup.c) / sup.b;
- path1.push_back({ m,y });
- path2.push_back({ m,y });
- }
- path2.push_back(a[i]);
- }
- }
- if ((a[0].x <= m && a[n - 1].x > m) || (a[n - 1].x <= m && a[0].x > m)) {
- pr sup = ur_pr(a[0], a[n - 1]);
- ld y = (-sup.a * m - sup.c) / sup.b;
- path1.push_back({ m,y });
- path2.push_back({ m,y });
- }
- return getSmn(path1) - getSmn(path2);
- }
- signed main() {
- #ifdef _DEBUG
- freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);
- #endif
- freopen("cut.in", "r", stdin);
- freopen("cut.out", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- ll t = 1;
- //cin >> t
- while (t--) {
- ll n, i, j, tt = 100;
- cin >> n;
- ld l = inf, r = -inf, m, ans = inf, id;
- vector <Point> a(n);
- for (i = 0; i < n; i++) {
- cin >> a[i].x >> a[i].y;
- l = min(l, a[i].x);
- r = max(r, a[i].x);
- }
- if (getSmn(a) > 0) {
- while (tt--) {
- m = (l + r) / 2.0;
- ld res = check(m, a);
- if (fabs(res) < ans) {
- ans = fabs(res);
- id = m;
- }
- if (res<= 0) {
- l = m;
- }
- else {
- r = m;
- }
- }
- cout << fixed << setprecision(6)
- << id << endl;
- }
- else {
- cout << fixed << setprecision(6)
- << (l + r) / 2.0 << endl;
- }
- }
- }
- //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement