Cod sursa(job #1202917)

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

const double pi = 3.141592653589;
const int maxn = 120005;

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

double min_x,min_y;
punct a[maxn];
int i,n,poz;
int t[maxn];

int semn_det(punct a,punct b,punct c){
    if(a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x>0) return 1;
    else return (-1);
}

double polar(double x,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;
                          else return 0.0;
                         }
}

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

int main(){
    fi>>n;
    for(i=1;i<=n;i++) fi>>a[i].x>>a[i].y;
    
    min_x=a[1].x; min_y=a[1].y;
    for(i=2;i<=n;i++)
      if(a[i].y<min_y){
                       min_x=a[i].x;
                       min_y=a[i].y;
                      }
    
    for(i=1;i<=n;i++) a[i].p=polar(a[i].x-min_x,a[i].y-min_y);
    
    sort(a+1,a+n+1,comp);
    
    t[1]=1; t[2]=2; poz=2;
    for(i=3;i<=n;i++)
      if(semn_det(a[t[poz-1]],a[t[poz]],a[i])>0) t[++poz]=i;
      else{
           while(semn_det(a[t[poz-1]],a[t[poz]],a[i])<0) poz--;
           t[++poz]=i;
          }
    
    fo<<poz<<"\n";
    for(i=1;i<=poz;i++) 
      fo<<fixed<<setprecision(7)<<a[t[i]].x<<" "<<fixed<<setprecision(7)<<a[t[i]].y<<"\n";
    
    fi.close();
    fo.close();
    return 0;
}