Cod sursa(job #1550093)

Utilizator PetruZZatic Petru PetruZ Data 13 decembrie 2015 10:43:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");

#define x first
#define y second

typedef pair<double,double> pn;

/*struct pn{
       double x,y;
       }v[120010];*/
     
pn stk[120010],v[120010];
int N, head;

double ccw(const pn& p1,const pn& p2,const pn& p3) // <0 dup acele cs // >0 impotriva acelor cs // =0 coliniare
{
       return( (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) );
       }
       
bool cmp(const pn& p1,const pn& p2){
     return (ccw(v[1],p1,p2)<0);
     }
    
///////////////////////////////////////////////////////////////////////////

int main() {
    
    pn mn;
    mn.x=1000000005;
    mn.y=1000000005;
    
    
    cin >> N;
    for(int i(1); i<=N; ++i){
            cin >> v[i].x >> v[i].y;
         /*   if( (v[i].x<mn.x)&&(v[i].y<mn.y) ) {
                                                mn.x=v[i].x;
                                                mn.y=v[i].y;
                                                poz=i;
                                                  } */
            }
    
	int poz=1;
    for(int i(2); i<=N; ++i) if(v[i]<v[poz]) poz=i;
     
    swap(v[1],v[poz]);
    sort(v+2, v+N+1, cmp);
    
    stk[1]=v[1]; stk[2]=v[2];
    head=2;
    for(int i=3; i<=N; ++i) {
                             while(head>=2 && ccw(stk[head-1],stk[head],v[i])>0) --head;
                             stk[++head]=v[i]; 
                              }
    
    cout << head << "\n";
    cout << fixed;
    
    for(int i=head; i>=1; --i) cout << setprecision(9) << stk[i].x << " " << stk[i].y << "\n";
    
    
    
    
    
return 0;    
}