Cod sursa(job #1188381)

Utilizator xtreme77Patrick Sava xtreme77 Data 19 mai 2014 15:11:27
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define PI 3.1415926535897
const int MAX = 1<<17;

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct infs{
    long double x,y;
};
infs q[MAX];
long double determin(infs a,infs b,infs c){
    return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);
}
bool comp(infs a,infs b){
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
bool cmp(infs a,infs b){
    return determin(q[1],a,b)<0;
}
int st[MAX],itmin,n,nr;
bool cmp2(int a,int b)
{
    return atan2(q[st[a]].y,q[st[a]].x)*180/PI>atan2(q[st[b]].y,q[st[b]].x)*180/PI;
}
void solve();
int main()
{
    //long double ymin=1<<29,xmin=1<<29;
    fin>>n;
    for(int i=1;i<=n;++i){
        fin>>q[i].x>>q[i].y;
       // if(ymin>q[i].y){
      //      ymin=q[i].y;
      //      itmin=i;
     //   }
      //  else if(ymin==q[i].y){
      //      if(xmin>q[i].x)xmin=q[i].x,itmin=i;
      //  }
    }
    //swap(q[itmin],q[1]);
    sort(q+1,q+n+1,comp);reverse(q+1,q+n+1);
    sort(q+2,q+n+1,cmp);
    solve();

    //sort(st+2,st+nr+1,cmp2);
    fout<<nr<<'\n';
    for(int i=nr;i>=1;--i)fout<<fixed<<setprecision(12)<<q[st[i]].x<<' '<<q[st[i]].y<<'\n';
    return 0;
}
void solve(){
    st[++nr]=1;
    st[++nr]=2;
    for(int i=3;i<=n;++i){
        while(nr>=2 and determin(q[st[nr]],q[st[nr-1]],q[i])<=0)--nr;
        st[++nr]=i;
    }
}