Cod sursa(job #1258368)

Utilizator mika17Mihai Alex Ionescu mika17 Data 8 noiembrie 2014 19:38:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef pair<double, double> Point;


double cross(const Point &p0, const Point &a,const Point &b) {

    double x1 = a.first - p0.first, y1 = a.second - p0.second,
      x2 = b.first - p0.first, y2 = b.second - p0.second;
    return x1 * y2 - x2 * y1;
}

struct cmp {

  Point p0;
  cmp(Point &p0) : p0(p0) {}
  bool operator() (const Point& a, const Point &b) {
    return cross(p0, a, b) > 0;
  }
};

int main() {

  ifstream f("infasuratoare.in");
  ofstream g("infasuratoare.out");

  int n;
  f>>n;
  
  vector<Point> P(n, Point());

  for(int i = 0; i < n;i ++) {
    f >> P[i].first >> P[i].second;
  }

  int min = 0;
  for(int i = 1; i < n; i++) {
    if(P[min] > P[i])
      min = i;
 }

  Point tmp = P[min];
  P[min] = P[0];
  P[0] = tmp;


  sort( P.begin() + 1, P.end() , cmp(P[0]));

  vector<int> S;
  S.push_back(0);
  S.push_back(1);
  
  for(int i = 2; i < n; i++) {

    while(S.size() > 1 && cross(P[S[S.size() - 2]], P[S[S.size() - 1]], P[i] ) < 0) {
      S.pop_back();
    }
    
    if(S.size() == 1 || cross(P[S[S.size() - 2]], P[S[S.size() - 1]], P[i] ) > 0)
      S.push_back(i);
  }

  g << S.size() << endl;
  g << setprecision(6) << fixed;
  for(int i = 0; i < S.size(); i++) {
    g << P[S[i]].first << ' ' << P[S[i]].second << endl;
  }

  return 0;
}