Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- using namespace std;
- struct vec2d {
- int x, y;
- inline void init(int x, int y) {
- this->x = x;
- this->y = y;
- }
- vec2d(int x, int y) {
- init(x, y);
- }
- vec2d() {}
- inline int cross(const vec2d &b) const {
- return x * b.y - b.x * y;
- }
- inline int operator%(const vec2d &b) const {
- return cross(b);
- }
- inline int sqlen() const {
- return x * x + y * y;
- }
- inline double len() const {
- return sqrt((double)sqlen());
- }
- inline vec2d operator-(const vec2d& b) const {
- return vec2d(x - b.x, y - b.y);
- }
- };
- // x1*y2 - x2*y1
- int n;
- vec2d a[20000];
- vector<vec2d> s;
- bool comp(const vec2d &a, const vec2d &b) {
- int q = a % b;
- if (q != 0) {
- return q > 0;
- }
- return a.sqlen() < b.sqlen();
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- //cout << vec2d(1, 1).cross(vec2d(1, 0)) << endl;
- cin >> n;
- int shx = 100500, shy = 100500;
- for (int i = 0; i < n; ++i) {
- cin >> a[i].x >> a[i].y;
- if (a[i].y < shy) {
- shy = a[i].y;
- shx = a[i].x;
- }
- if (a[i].x < shx && a[i].y == shy) {
- shx = a[i].x;
- }
- }
- //cout << "shift by" << shx << " " << shy << endl;
- for (int i = 0; i < n; ++i) {
- a[i].x -= shx;
- a[i].y -= shy;
- }
- sort(a, a + n, comp);
- for (int i = 0; i < n; ++i) {
- unsigned k;
- while ((k = s.size()) >= 2 && (s[k - 1] - s[k - 2]) % (a[i] - s[k - 1]) <= 0) {
- s.pop_back();
- }
- s.push_back(a[i]);
- }
- /*for (unsigned i = 0; i < s.size(); ++i) {
- cout << s[i].x << " " << s[i].y << "\n";
- }*/
- s.push_back(s.front());
- double p = 0;
- for (unsigned i = 1; i < s.size(); ++i) {
- p += (s[i - 1] - s[i]).len();
- //cout << ":" << "(" << a[i].x << ", " << a[i].y << ")" << (a[i - 1] - a[i]).len() << " ";
- }
- cout << p << endl;
- long long sq2 = 0;
- for (unsigned i = 1; i < s.size(); ++i) {
- sq2 += (s[i - 1].x - s[i].x) * (s[i - 1].y + s[i].y);
- }
- cout << sq2 / 2 << (sq2 % 2? ".5" : "") << endl;
- //cout << sq2 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement