Cod sursa(job #2333475)

Utilizator sichetpaulSichet Paul sichetpaul Data 1 februarie 2019 10:22:39
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define DIM 120001
using namespace std;
int st1[DIM],st2[DIM];
struct punct{
   double x,y;
};
punct v[DIM];
bool cmp(punct a,punct b) {
  if (a.x==b.x) return a.y<b.y;
  return a.x<b.x;
}
double cross(int p0,int p1,int p2) {
    return (v[p1].x-v[p0].x)*(v[p2].y-v[p0].y)-(v[p2].x-v[p0].x)*(v[p1].y-v[p0].y);
}
int main()
{  int nr1,nr2,i,n;
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    for (i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);

    st1[1]=1,st1[2]=2;
    nr1=2;
    for (i=3;i<=n;++i) {
        while (nr1>=2 && cross(st1[nr1-1],st1[nr1],i)<0)
            --nr1;
        st1[++nr1]=i;
    }

    st2[1]=n,st2[2]=n-1;
    nr2=2;
    for (i=n-2;i>=1;--i) {
        while (nr2>=2 && cross(st2[nr2-1],st2[nr2],i)<0)
            --nr2;
        st2[++nr2]=i;
    }

    g<<nr1+nr2-2<<'\n';
    for (i=1;i<=nr1;++i)
        g<<setprecision(12)<<fixed<<v[st1[i]].x<<" "<<v[st1[i]].y<<'\n';
    for (i=2;i<nr2;++i)
        g<<setprecision(12)<<fixed<<v[st2[i]].x<<" "<<v[st2[i]].y<<'\n';
    return 0;
}