Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <ctime>
- #include <random>
- #include <cmath>
- #include <bitset>
- #include <iomanip>
- #include <list>
- using namespace std;
- typedef long long ll;
- struct point {
- ll x, y;
- point() : x(0), y(0) {}
- point(ll xx, ll yy) {
- x = xx;
- y = yy;
- }
- void scan() {
- cin >> x >> y;
- }
- void print() {
- cout << x << " " << y << "\n";
- }
- ll operator*(const point &p) const {
- return x * p.x + y * p.y;
- }
- ll operator%(const point &p) const {
- return x * p.y - y * p.x;
- }
- bool operator==(const point &p) const {
- return x == p.x && y == p.y;
- }
- point operator-(const point &p) const {
- return point(x - p.x, y - p.y);
- }
- point operator+(const point &p) const {
- return point(x + p.x, y + p.y);
- }
- bool is_on_line(point &A, point &B) {
- return (((A - *this) % (B - *this)) == 0);
- }
- bool is_on_segment(point &A, point &B) {
- return (*this).is_on_line(A, B) && ((A - *this) * (B - *this) <= 0);
- }
- double length() {
- return sqrt(double((*this) * (*this)));
- }
- ll sqr_len() {
- return x * x + y * y;
- }
- double dist_to(const point &A, const point &B) const {
- ll cur = abs((A - *this) % (B - *this));
- return (double)cur / (A - B).length();
- }
- };
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n;
- cin >> n;
- vector <point> polygon(n);
- for (int i = 0; i < n; ++i) {
- polygon[i].scan();
- }
- for (int i = 1; i < n; ++i) {
- if (polygon[i].x < polygon[0].x || (polygon[i].x == polygon[0].x && polygon[i].y < polygon[0].y)) {
- swap(polygon[0], polygon[i]);
- }
- }
- sort(polygon.begin() + 1, polygon.end(), [&](const point &s, const point &f) {
- if((s - polygon[0]) % (f - polygon[0]) != 0) {
- return (s - polygon[0]) % (f - polygon[0]) > 0;
- }
- else {
- return (s - polygon[0]).sqr_len() < (f - polygon[0]).sqr_len();
- }
- });
- vector <point> s;
- s.push_back(polygon[0]);
- s.push_back(polygon[1]);
- for (int i = 2; i < n; ++i) {
- while (s.size() > 1 && (s[s.size() - 2] - s.back()) % (polygon[i] - s.back()) >= 0) {
- s.pop_back();
- }
- s.push_back(polygon[i]);
- }
- double P = 0;
- double S = 0;
- s.push_back(s[0]);
- for (int i = 0; i + 1 < s.size(); ++i) {
- P += (s[i + 1] - s[i]).length();
- S += s[i] % s[i + 1];
- }
- S /= 2;
- S = abs(S);
- cout << fixed << setprecision(16) << P << endl << S << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement