Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(l) cerr<<#l<<' '<<l<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- typedef long double ld;
- #define Vec Point
- const ld EPS = 1e-13;
- const ld Pi = 3.14159265358979323846;
- int sign(ld x) {
- if (x > EPS) return 1;
- if (x < -EPS) return -1;
- return 0;
- }
- ld sq(ld x) {
- return x * x;
- }
- struct Point {
- ld x, y;
- Point() : x(0), y(0) {}
- Point(ld _x, ld _y) : x(_x), y(_y) {}
- Point operator-(const Point& other) const {
- return Point(x - other.x, y - other.y);
- }
- Point operator+(const Point& other) const {
- return Point(x + other.x, y + other.y);
- }
- Point operator*(const ld& other) const {
- return Point(x * other, y * other);
- }
- ld operator^(const Point& other) const {
- return x * other.y - y * other.x;
- }
- ld operator*(const Point& other) const {
- return x * other.x + y * other.y;
- }
- ld len2() const {
- return sq(x) + sq(y);
- }
- ld len() const {
- return sqrtl(len2());
- }
- Point norm() const {
- ld d = len();
- return Point(x / d, y / d);
- }
- bool operator<(const Point& other) const {
- if (sign(x - other.x) != 0) {
- return x < other.x;
- }
- else if (sign(y - other.y) != 0) {
- return y < other.y;
- }
- return false;
- }
- bool operator==(const Point& other) const {
- return sign(x - other.x) == 0 && sign(y - other.y) == 0;
- }
- Point ort() {
- return Point(-y, x);
- }
- void deb() const {
- std::cerr << "(" << x << ", " << y << ")" << std::endl;
- }
- };
- ostream& operator << (ostream& out, const Point& val) {
- return out << val.x << ' ' << val.y;
- }
- istream& operator >> (istream& in, Point& val) {
- return in >> val.x >> val.y;
- }
- struct Line {
- ld a, b, c;
- Line() : a(0), b(0), c(0) {}
- Line(const Point& x, const Point& y) : a(y.y - x.y), b(x.x - y.x), c(x.y* y.x - y.y * x.x) {
- ld d = Point(a, b).len();
- a /= d, b /= d, c /= d;
- if (sign(a) == -1) {
- a = -a;
- b = -b;
- c = -c;
- }
- else if (sign(a) == 0 && sign(b) == 0) {
- a = 0;
- b = -b;
- c = -b;
- }
- }
- bool operator==(const Line& other) const {
- return sign(a - other.a) == 0 && sign(b - other.b) == 0 && sign(c - other.c) == 0;
- }
- };
- ld get_S(vector<Point>& p) {
- int n = (int)p.size();
- ld ans = 0.0000000;
- for (int i = 0; i < n; i++) {
- ans += (p[i] ^ p[i + 1 < n ? i + 1 : 0]);
- }
- return fabs(ans) / 2.0000;
- }
- bool line_cross(const Line& a, const Line& b, Point& ans) {
- ld d = (a.b * b.a - a.a * b.b);
- if (sign(d) == 0)
- return false;
- ans.x = (b.b * a.c - b.c * a.b) / d;
- ans.y = (b.c * a.a - a.c * b.a) / d;
- return true;
- }
- bool is_point_on_seg(const Point& a, const Point& b, const Point& x) {
- return sign((a - b).len() - (a - x).len() - (b - x).len()) == 0;
- }
- void revector(vector<Point>& sub) {
- for (int i = 1; i < (int)sub.size();i++) {
- sub[i] = sub[i] - sub[0];
- }
- }
- void addvector(vector<Point>& sub) {
- for (int i = 1; i < (int)sub.size(); i++) {
- sub[i] = sub[i] + sub[0];
- }
- }
- bool check(vector<Point>& p, ld& mid) {
- auto cmp = [&](const Point& a, const Point& b) {
- if (sign(a ^ b)) {
- return sign(a ^ b) == 1;
- }
- else {
- return sign(b.len2() - a.len2()) == 1;
- }
- };
- Line ins(Point(mid, 0), Point(mid, 1));
- vector<Point> left, right;
- for (int i = 0; i < (int)p.size(); i++) {
- if (sign(p[i].x - mid) == 1) {
- right.push_back(p[i]);
- }
- else {
- left.push_back(p[i]);
- }
- Point ans;
- if (line_cross(Line(p[i], p[i + 1 < (int)p.size() ? i + 1 : 0]), ins, ans)) {
- if (is_point_on_seg(p[i], p[i + 1 < (int)p.size() ? i + 1 : 0], ans)) {
- left.push_back(ans);
- right.push_back(ans);
- }
- }
- }
- revector(left), revector(right);
- if(!left.empty())stable_sort(left.begin() + 1, left.end(), cmp);
- if(!right.empty())stable_sort(right.begin() + 1, right.end(), cmp);
- addvector(left), addvector(right);
- return sign((get_S(left) - get_S(right))) == 1;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- freopen("cut.in", "r", stdin);
- freopen("cut.out", "w", stdout);
- cout << fixed << setprecision(6);
- int n;
- cin >> n;
- vector<Point> p(n);
- for (int i = 0; i < n; i++) {
- cin >> p[i];
- }
- ld l = -1e3 - 1, r = 1e3 + 1;
- for (int lg = 0; lg < 200; lg++) {
- ld m = (l + r) / 2.0;
- if (check(p, m)) {
- r = m;
- }
- else {
- l = m;
- }
- }
- cout << r;
- }
Add Comment
Please, Sign In to add comment