Cod sursa(job #1249797)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 27 octombrie 2014 15:07:01
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");

struct punct{
       double x;
       double y;
       double p;
};

const double PI = 3.14159265;
const int MAX_N = 120005;

int i,n,poz_min;
int st[MAX_N],k;
punct a[MAX_N];

short int semn(const punct &A, const punct &B, const punct &P){
      double x = (B.x*P.y + A.x*B.y + A.y*P.x - B.x*A.y - P.x*B.y - P.y*A.x);
      if(x>0) return 1;
      if(x<0) return (-1);
      return 0;
}

double polar(const double &x, const double &y){
       if(x>0){
               if(y>0) return atan(y/x);
               else return atan(y/x)+2*PI;
              }
       else if(x<0) return atan(y/x)+PI;
            else if(x==0){
                          if(y>0) return PI/2;
                          else if(y<0) return 3*PI/2;
                         }           
       return 0;
}

bool comp(const punct &a, const punct &b){
     return (a.p<b.p);
}

int main(){
    fi>>n;
    for(i=1;i<=n;i++) fi>>a[i].x>>a[i].y;
    
    poz_min=1;
    for(i=1;i<=n;i++)
      if(a[i].y<a[poz_min].y) poz_min=i;
    for(i=1;i<=n;i++)
      if(a[i].y==a[poz_min].y && a[i].x<a[poz_min].x) poz_min=i;
    
    for(i=1;i<=n;i++)
      a[i].p = polar(a[i].x-a[poz_min].x,a[i].y-a[poz_min].y);
    
    sort(a+1,a+n+1,comp);
    
    st[1]=1; st[2]=2; k=2;
    for(i=3;i<=n;i++)
      if(semn(a[st[k-1]],a[st[k]],a[i])>0) st[++k]=i;
      else{
           while(k>1 && semn(a[st[k-1]],a[st[k]],a[i])<=0) k--;
           if(semn(a[st[k-1]],a[st[k]],a[i])!=0)
           st[++k]=i;
          }
    
    fo<<k<<'\n';
    for(i=1;i<=k;i++)
      fo<<fixed<<setprecision(8)<<a[st[i]].x<<' '<<fixed<<setprecision(8)<<a[st[i]].y<<'\n';
    
    fi.close();
    fo.close();
    return 0;
}