Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <iomanip>
- #include <string>
- #include <cmath>
- #include <set>
- #include <map>
- #include <algorithm>
- using namespace std;
- struct point
- {
- int x, y;
- point()
- {
- x = 0, y = 0;
- }
- point(int _x, int _y)
- {
- x = _x;
- y = _y;
- }
- point(point a, point b)
- {
- x = b.x - a.x;
- y = b.y - a.y;
- }
- bool operator<(point p) const
- {
- return (x < p.x || (x == p.x && y < p.y));
- }
- };
- point start;
- bool cmp(point a, point b)
- {
- double anglea = atan2(a.x - start.x, a.y - start.y);
- double angleb = atan2(b.x - start.x, b.y - start.y);
- if (anglea < 0)
- {
- anglea += 2 * (3.14159265);
- }
- if (angleb < 0)
- {
- angleb += 2 * (3.14159265);
- }
- return anglea < angleb;
- }
- int vm(point a, point b) {
- return a.x * b.y - a.y * b.x;
- }
- void bhull(vector<point> points, vector<point> &hull)
- {
- stable_sort(points.begin(), points.end());
- start = points[0];
- stable_sort(points.begin() + 1, points.end(), cmp);
- hull = vector<point>(points.begin(), points.begin() + 2);
- for (int i = 2; i < points.size(); i++)
- {
- if (hull.size() < 3)
- {
- hull.push_back(points[i]);
- continue;
- }
- point a = hull[hull.size() - 2];
- point b = hull[hull.size() - 1];
- point c = points[i];
- while (hull.size() > 2)
- {
- if (vm(point(a, b), point(b, c)) >= 0)
- {
- hull.pop_back();
- if (hull.size() < 3)
- {
- break;
- }
- a = hull[hull.size() - 2];
- b = hull[hull.size() - 1];
- c = points[i];
- }
- }
- hull.push_back(points[i]);
- }
- }
- double ar(vector<point> points)
- {
- double a = 0;
- for (int i = 0; i < points.size(); i++)
- {
- a += vm(points[i], points[(i + 1) % points.size()]);
- }
- return a / 2;
- }
- int main()
- {
- int n;
- cin >> n;
- vector<point> points(n);
- for (int i = 0; i < n; i++)
- {
- cin >> points[i].x >> points[i].y;
- }
- double r = 1e12;
- for (int first = 0; first < n; first++)
- {
- for (int second = first + 1; second < n; second++)
- {
- point f = points[first];
- point s = points[second];
- vector<point> fp;
- vector<point> sp;
- for (int i = 0; i < n; i++)
- {
- if (i != first && i != second)
- {
- point p = points[i];
- if (vm(point(f, s), point(s, p)) < 0)
- {
- sp.push_back(p);
- }
- else
- {
- fp.push_back(p);
- }
- }
- }
- vector<point> fh;
- vector<point> sh;
- fp.push_back(f);
- sp.push_back(s);
- if (fp.size() > 2 && sp.size() > 2)
- {
- bhull(fp, fh);
- bhull(sp, sh);
- r = min(r, abs(ar(fh) - ar(sh)));
- }
- fp.pop_back();
- sp.pop_back();
- fp.push_back(s);
- sp.push_back(f);
- if (fp.size() > 2 && sp.size() > 2)
- {
- bhull(fp, fh);
- bhull(sp, sh);
- r = min(r, abs(ar(fh) - ar(sh)));
- }
- fp.pop_back();
- sp.pop_back();
- fp.push_back(f);
- fp.push_back(s);
- if (fp.size() > 2 && sp.size() > 2)
- {
- bhull(fp, fh);
- bhull(sp, sh);
- r = min(r, abs(ar(fh) - ar(sh)));
- }
- fp.pop_back();
- fp.pop_back();
- sp.push_back(f);
- sp.push_back(s);
- if (fp.size() > 2 && sp.size() > 2)
- {
- bhull(fp, fh);
- bhull(sp, sh);
- r = min(r, abs(ar(fh) - ar(sh)));
- }
- sp.pop_back();
- sp.pop_back();
- }
- }
- cout << fixed << setprecision(6) << r;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement