Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,ssse3,sse3,sse4,avx,avx2,popcnt,tune=native")
- #include <iostream>
- #include <vector>
- #include <string>
- #include <queue>
- #include <set>
- #include <iomanip>
- #include <map>
- #include <algorithm>
- #include <cmath>
- #include <bitset>
- #include <limits.h>
- using namespace std;
- struct Vector {
- long double x; long double y;
- Vector(long double _x = 0, long double _y = 0) {
- x = _x;
- y = _y;
- }
- };
- Vector mn = { 1e12, 1e12 };
- long double operator^(Vector a, Vector b) {
- return (a.x * b.y - a.y * b.x);
- }
- Vector operator-(Vector a, Vector b) {
- return { a.x - b.x, a.y - b.y };
- }
- bool operator==(Vector a, Vector b) {
- return (a.x == b.x && a.y == b.y);
- }
- long double len(Vector a) {
- return sqrt(a.x * a.x + a.y * a.y);
- }
- bool comp(Vector a, Vector b) {
- Vector f = a - mn, s = b - mn;
- if ((f ^ s) > 0) return true;
- else if ((f ^ s) == 0 && len(a) > len(b)) return true;
- else return false;
- }
- istream& operator>>(istream& in, Vector& a) {
- in >> a.x >> a.y;
- return in;
- }
- ostream& operator<<(ostream& out, Vector& a) {
- out << a.x << " " << a.y;
- return out;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- vector<Vector> a(n);
- map<Vector, int> m;
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- m[a[i]] = i + 1;
- if (a[i].y < mn.y || (a[i].y == mn.y && a[i].x < mn.x)) {
- mn = a[i];
- }
- }
- auto it = unique(a.begin(), a.end());
- a.resize(distance(a.begin(), it));
- n = (int)a.size();
- int index = 0;
- for (int i = 0; i < n; ++i) {
- if (a[i] == mn) {
- index = i;
- break;
- }
- }
- swap(a[0], a[index]);
- sort(a.begin() + 1, a.end(), comp);
- vector<Vector> ans;
- ans.push_back(a[0]);
- ans.push_back(a[1]);
- for (int i = 2; i < n; ++i) {
- while (ans.size() > 1 &&
- ((a[i] - ans[(int)ans.size() - 1]) ^ (ans[(int)ans.size() - 1] - ans[(int)ans.size() - 2])) >= 0) {
- ans.pop_back();
- }
- ans.push_back(a[i]);
- }
- long double p = 0, s = 0;
- ans.push_back(ans[0]);
- for (int i = 1; i < (int)ans.size(); ++i) {
- p += len(ans[i] - ans[i - 1]);
- s += (ans[i] ^ ans[i - 1]);
- }
- cout << ans.size() - 1 << "\n";
- for (int i = 0; i < (int)ans.size() - 1; ++i) {
- cout << m[a[i]] << " ";
- }
- cout << "\n";
- cout << fixed << setprecision(13) << p << "\n" << fabs(s / 2.0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement