Cod sursa(job #1802790)

Utilizator DjokValeriu Motroi Djok Data 10 noiembrie 2016 17:28:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<bits/stdc++.h>
using namespace std;

struct point {
  double x, y;

  bool operator < (point &b) {
    if(x == b.x) return y < b.y;
    return x < b.x;
  }
};

int i, n;
point a[120005];
vector<point> up, down, ans;

double area(point a, point b, point c) { return a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * b.y; }

bool cw(point a, point b, point c) { return area(a, b, c) < 0; }

bool ccw(point a, point b, point c) {return area(a, b, c) > 0; }

int main()
{
  ifstream cin("infasuratoare.in");
  ofstream cout("infasuratoare.out");

  ios_base::sync_with_stdio(0);

  cin >> n;
  for(i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;

  sort(a + 1, a + n + 1);

  up.push_back(a[1]); down.push_back(a[1]);

  for(i = 2; i <= n; ++i) {
    if(i == n || cw(a[1], a[i], a[n])) {
      while(up.size() > 1 && !cw(up[up.size() - 2], up[up.size() - 1], a[i])) up.pop_back();
      up.push_back(a[i]);
    }

    if(i == n || ccw(a[1], a[i], a[n])) {
      while(down.size() > 1 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i])) down.pop_back();
      down.push_back(a[i]);
    }
  }

  down.pop_back();
  reverse(down.begin(), down.end());
  down.pop_back();

  for(auto it : down) up.push_back(it);

  cout << up.size() << '\n';
  for(auto it : up) cout << setprecision(8) << fixed << it.x << ' ' << it.y << '\n';

  return 0;
}