Cod sursa(job #1303567)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 28 decembrie 2014 04:05:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {double x,y;}v[102],s[102],pmin;
int k,n,i;
double produs(punct p1,punct p2,punct p3){
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int cadran(punct p){
    if(p.x>=pmin.x && p.y>=pmin.y)
        return 1;
    if(p.x<pmin.x && p.y>=pmin.y)
        return 2;
    if(p.x<pmin.x && p.y<pmin.y)
        return 3;
    if(p.x>=pmin.x && p.y<pmin.y)
        return 4;
}
double distpatrat(punct a){
    return (a.x-pmin.x)*(a.x-pmin.x)+(a.y-pmin.y)*(a.y-pmin.y);
}
int cmp(punct a,punct b){
    int c1=cadran(a);
    int c2=cadran(b);
    if(c1>c2)
        return 0;
    if(c1<c2)
        return 1;
    if(produs(pmin,a,b)<0)
        return 0;
    if(produs(pmin,a,b)==0 && distpatrat(a)>distpatrat(b) && c1==c2)
        return 0;
    return 1;
}
void PUSH(punct x){
    s[++k]=x;
}
void POP(){
    k--;
}
void afis(){
    fout<<k<<'\n';
    for(int i=1;i<=k;i++)
        fout<<setprecision(6)<<fixed<<v[i].x<<" "<<setprecision(6)<<fixed<<v[i].y<<'\n';
}
void Graham(){
    int i;
    double o;
    sort(v+1,v+n+1,cmp);
    k=0;
    PUSH(v[1]);
    PUSH(v[2]);
    for(i=3;i<=n;i++){
        o=produs(s[k-1],s[k],v[i]);
        if(o==0){
            POP();
            PUSH(v[i]);
        }
        else{
            if(o>0)
                PUSH(v[i]);
            else{
                while(o<=0 && k>1){
                    POP();
                    o=produs(s[k-1],s[k],v[i]);
                }
                PUSH(v[i]);
            }
        }
    }
    afis();
}
int main(){
    fin>>n;
    pmin.x=3200;
    pmin.y=3200;
    for(i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        if(v[i].x<=pmin.x && v[i].y<=pmin.y)
            pmin=v[i];
    }
    Graham();
    fin.close();fout.close();
    return 0;
}