Cod sursa(job #1608312)

Utilizator c0rn1Goran Cornel c0rn1 Data 21 februarie 2016 23:20:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int n;
struct Point{
   double x, y;
   Point(double x = 0, double y = 0): x(x), y(y) {}
   bool operator()(Point A, Point B){
      if (A.x != B.x)
         return A.x < B.x;
      return A.y < B.y;
   }
};
vector<Point> elem, v1, v2;

void readData(){
   double x, y;
   scanf("%d\n", &n);
   for (int i = 0; i < n; ++i){
      scanf("%lf %lf\n", &x, &y);
      elem.push_back(Point(x, y));
   }
}

double det(Point A, Point B, Point C){
   return A.x*B.y + B.x*C.y + C.x*A.y - B.y*C.x - A.y*B.x - A.x*C.y;
}

void insertElement(vector<Point> &v, Point p){
   while (v.size() >= 2 && det(v[v.size()-2], v[v.size()-1], p)<=0)
      v.pop_back();
   v.push_back(p);
}

void solve(){
   sort(elem.begin(), elem.end(), Point());
   for (int i = 0; i < elem.size(); ++i)
      insertElement(v1, elem[i]);
   v2.push_back(v1[v1.size()-1]);
   for (int i = elem.size()-1; i >= 0; --i)
      insertElement(v2, elem[i]);
   v1.pop_back(); v2.pop_back();
   for (int i = 0; i < v2.size(); ++i)
      v1.push_back(v2[i]);

   printf("%d\n", v1.size());
   for (int i = 0; i < v1.size(); ++i)
      printf("%lf %lf\n", v1[i].x, v1[i].y);
}

int main()
{
   freopen("infasuratoare.in", "r", stdin);
   freopen("infasuratoare.out", "w", stdout);
   readData();
   solve();

   return 0;
}