Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- long long inf = 1e16;
- struct vec {
- ll x, y;
- vec() {
- x = rand() % 20000 - 10000;
- y = rand() % 20000 - 10000;
- }
- vec(ll a, ll b) {
- x = a, y = b;
- }
- vec(vec a, vec b) {
- x = b.x - a.x;
- y = b.y - a.y;
- }
- void make_vec(vec a, vec b) {
- x = b.x - a.x;
- y = b.y - a.y;
- }
- };
- istream& operator >>(istream& in, vec &a) {
- in >> a.x >> a.y;
- return in;
- }
- ostream& operator <<(ostream& os, vec &a) {
- os << a.x << ' ' << a.y;
- return os;
- }
- ll operator ^(vec a, vec b) {
- return a.x * b.y - a.y * b.x;
- }
- ll operator *(vec a, vec b) {
- return a.x * b.x + a.y * b.y;
- }
- vec start;
- bool cmp1(vec a, vec b) {
- return a.y < b.y || a.y == b.y && a.x < b.x;
- }
- bool cmp2(vec a, vec b) {
- vec f(start, a), s(start, b);
- return ((f ^ s) > 0) || ((f ^ s) == 0 && (a * a < b * b));
- }
- string solve1(vector<vec> p) {
- sort(p.begin(), p.end(), cmp1);
- start = p[0];
- sort(p.begin() + 1, p.end(), cmp2);
- vector <vec> cnv;
- for (int i = 0; i < p.size(); ++i) {
- while (cnv.size() > 1) {
- vec a(cnv[cnv.size() - 2], cnv[cnv.size() - 1]),
- b(cnv[cnv.size() - 2], p[i]);
- if ((a ^ b) <= 0)
- cnv.pop_back();
- else
- break;
- }
- cnv.push_back(p[i]);
- }
- cnv.push_back(start);
- vec o(0, 0);
- ld per = 0, ar = 0;
- for (int i = 0; i < cnv.size() - 1; ++i) {
- vec e(cnv[i], cnv[i + 1]);
- per += sqrt(e * e);
- vec a(o, cnv[i]),
- b(o, cnv[i + 1]);
- ar += (a ^ b);
- }
- string s = "";
- ostringstream os(s);
- os << fixed << setprecision(10);
- os << per << '\n' << fabsl(ar / 2.0);
- return os.str();
- }
- #define pb push_back
- #define ppb pop_back
- #define double long double
- #define int long long
- const double eps = 1e-9;
- struct point {
- int x, y;
- point(){}
- point(int x, int y) : x(x), y(y) {}
- };
- struct Vector {
- int x, y;
- Vector(){}
- Vector(point a, point b) {
- x = b.x-a.x;
- y = b.y-a.y;
- }
- Vector(point a) {
- x = a.x;
- y = a.y;
- }
- };
- istream& operator >> (istream& is, point& p) {
- is >> p.x >> p.y;
- return is;
- }
- bool cmp(point a, point b) {
- return a.x < b.x || a.x == b.x && a.y < b.y;
- }
- int operator * (Vector a, Vector b) {
- return a.x*b.x+a.y*b.y;
- }
- int operator ^ (Vector a, Vector b) {
- return a.x*b.y-a.y*b.x;
- }
- bool cw(point a, point b, point c) {
- return (Vector(a, b)^Vector(a, c)) < 0;
- }
- bool ccw(point a, point b, point c) {
- return (Vector(a, b)^Vector(a, c)) > 0;
- }
- vector<point> convex_hull(vector<point> v) {
- vector<point> up, pu;
- sort(v.begin(), v.end(), &cmp);
- point p1 = v[0];
- point p2 = v.back();
- up.pb(p1); pu.pb(p1);
- for (int i = 1; i < v.size(); ++i) {
- point c = v[i];
- if (cw(p1, c, p2) || i == v.size()-1) {
- while(up.size() > 1 && !cw(up[up.size()-2], up[up.size()-1], c))
- up.ppb();
- up.pb(c);
- }
- if (ccw(p1, c, p2) || i == v.size()-1) {
- while(pu.size() > 1 && !ccw(pu[pu.size()-2], pu[pu.size()-1], c))
- pu.ppb();
- pu.pb(c);
- }
- }
- vector<point> ans;
- for (int i = 0; i < up.size(); ++i) {
- ans.pb(up[i]);
- }
- for (int i = pu.size()-2; i > 0; --i)
- ans.pb(pu[i]);
- return ans;
- }
- double dist(point a, point b) {
- double x = b.x-a.x;
- double y = b.y-a.y;
- return sqrt(x*x+y*y);
- }
- string solve2(vector<point> v) {
- vector<point> hull = convex_hull(v);
- double per = dist(hull[0], hull.back());
- for (int i = 1; i < hull.size(); ++i) {
- per += dist(hull[i], hull[i-1]);
- }
- double sq = (Vector(hull.back())^Vector(hull[0]));
- // cout << sq << endl;
- for (int i = 1; i < hull.size(); ++i) {
- sq += Vector(hull[i-1])^Vector(hull[i]);
- // cout << sq << endl;
- }
- string s = "";
- ostringstream os(s);
- os << fixed << setprecision(10) << per << endl << abs(sq*0.5);
- return os.str();
- }
- int32_t main() {
- srand(time(NULL));
- for (int i = 0; i < 10000; ++i) {
- int n = rand() % 10 + 1;
- vector <vec> p(n);
- for (int i = 0; i < n; ++i) {
- p[i] = vec();
- }
- vector<point> v(n);
- for (int i = 0; i < n; ++i) {
- v[i] = point(p[i].x, p[i].y);
- }
- string ans1 = solve1(p);
- string ans2 = solve2(v);
- if (ans1 != ans2) {
- cout << "ALERTALERT\n";
- cout << n << endl;
- for (auto vv : p) {
- cout << vv << endl;
- }
- cout << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment