Cod sursa(job #1550087)

Utilizator PetruZZatic Petru PetruZ Data 13 decembrie 2015 10:20:02
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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


struct pn{
       double x,y;
       }v[120010];
       
pn stk[120010];

double ccw(pn p1, pn p2, 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(pn p1, pn p2){
     return (ccw(v[1],p1,p2)<0);
     }
     




int N, head;

///////////////////////////////////////////////////////////////////////////

int main() {
    
    pn mn;
    mn.x=1000000005;
    mn.y=1000000005;
    int poz;
    
    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;
                                                  }
            }
     
    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;    
}