Cod sursa(job #1883174)

Utilizator andreey_047Andrei Maxim andreey_047 Data 17 februarie 2017 19:36:08
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 120005;

int N,poz,wx,wy,top;

inline double cross_product(double x1,double y1,double x2,double y2,double x3,double y3){
  return (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
}

struct el{
  double x,y;
  bool operator <(const el&A) const
  {
      if(x == A.x)return y < A.y;
      return x < A.x;
  }
}a[nmax],st[nmax];

inline void Solve(){
  int i;
  top = 2;

  st[1] = a[1];
  st[2] = a[2];
  for(i = 3; i <= N; ++i){
    while(top >= 2 && cross_product(st[top-1].x,st[top-1].y,st[top].x,st[top].y,a[i].x,a[i].y)>0)
        --top;
    st[++top] = a[i];
  }


}

int main(){
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int i;
    f >> N;
    for(i = 1; i <= N; ++i)
        f >> a[i].x >> a[i].y;

    sort(a+1,a+N+1);
    Solve();
    g << top << '\n';

    for(i = top; i; --i)
        g <<fixed <<setprecision(6) << st[i].x << ' ' << st[i].y << '\n';

    f.close();
    g.close();
    return 0;
}