Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define pf push_front
- #define mp make_pair
- #define F first
- #define S second
- #define all(x) ((x).begin (), (x).end ())
- #define sz(a) (a).size()
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair < ull, ull > puu;
- const int N = (int)1e6 + 10;
- const puu base = mp(2017, 197);
- const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
- int n;
- struct Point {
- long double x, y;
- };
- struct vec {
- long double x, y;
- vec () {
- x = y = 0;
- }
- vec (Point a, Point b) {
- x = (b.x - a.x), y = (b.y - a.y);
- }
- };
- vector < Point > d, all, up, down;
- bool cmp (Point a, Point b) {
- return a.x < b.x || (a.x == b.x && a.y < b.y);
- }
- long long area (Point p1, Point p2, Point p3) {
- return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
- }
- bool cwise (Point p1, Point p2, Point p3) {
- return area (p1, p2, p3) < 0;
- }
- bool ccwise (Point p1, Point p2, Point p3) {
- return area (p1, p2, p3) > 0;
- }
- long double calc (Point p1, Point p2, Point p3) {
- vec a, b;
- a = vec (p2, p1);
- b = vec (p2, p3);
- //double cosinus = (a.x * b.x + a.y * b.y) / (sqrt (a.x * a.x + a.y * a.y) * sqrt (b.x * b.x + b.y * b.y));
- //cout << cosinus << endl;
- //return (long double)(((1. * acos (cosinus)) * 180.) / acos (-1.));
- double ang = fabs(atan2 (a.y, a.x) - atan2 (b.y, b.x));
- if (ang > acos (-1)) ang = 2. * acos (-1) - ang;
- //cout << ang << endl;
- ang = (ang * 180.) / acos (-1);
- //cout << ang << endl;
- return ang;
- }
- int main () {
- cin >> n;
- for (int i = 1; i <= n; ++i) {
- Point v;
- cin >> v.x >> v.y;
- d.pb (v);
- }
- sort (d.begin (), d.end (), &cmp);
- Point p1 = d[0], p2 = d.back ();
- up.pb (p1);
- down.pb (p1);
- for (int i = 1; i < sz (d); ++i) {
- if (i == sz (d) - 1 || cwise (p1, d[i], p2)) {
- while (sz (up) >= 2 && !cwise (up[sz(up) - 2], up[sz(up) - 1], d[i]))
- up.pop_back ();
- up.pb (d[i]);
- }
- if (i == sz (d) - 1 || ccwise (p1, d[i], p2)) {
- while (sz (down) >= 2 && !ccwise (down[sz(down) - 2], down[sz(down) - 1], d[i]))
- down.pop_back ();
- down.pb (d[i]);
- }
- }
- for (int i = 0; i < sz (up); ++i)
- all.pb (up[i]);
- for (int i = sz (down) - 2; i > 0; --i)
- all.pb (down[i]);
- long double ans = 1e12;
- //cout << sz (all) << endl;
- ans = min (ans, calc (all[1], all[0], all[all.size() - 1]));
- ans = min (ans, calc (all[all.size() - 2], all[all.size() - 1], all[0]));
- //cout << ans << endl;
- for (int i = 1; i < sz (all) - 1; ++i) {
- long double alpha = calc (all[i - 1], all[i], all[i + 1]);
- //cout << alpha << endl;
- ans = min (ans, alpha);
- }
- cout << fixed << setprecision (4) << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement