Cod sursa(job #1922583)

Utilizator Julian.FMI Caluian Iulian Julian. Data 10 martie 2017 17:58:27
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
#define nmax 10009
using namespace std;
int xmin,ymin;
void afisare();
struct punct{
double x,y,tg;
}p[nmax];

stack<int> S;

bool cmp(punct a,punct b){
    return a.tg<b.tg;
}

bool arie(double x1,double y1,double x2,double y2,double x3,double y3){
    int arie=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
    return arie>=0;
}

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int main(){
int n,i;
fin>>n;
int org=1;
for(i=1;i<=n;i++)
{
    fin>>p[i].x>>p[i].y;
    if(p[org].x > p[i].x || (p[org].x==p[i].x && p[org].y>p[i].y))org=i;
}

xmin=p[org].x;
ymin=p[org].y;
swap(p[1],p[org]);
p[1].x=0;p[1].y=0;
p[n+1]=p[1];

for(i=2;i<=n;i++)
{
    p[i].x-=xmin;
    p[i].y-=ymin;
    if(p[i].x==0)p[i].tg=1<<30;
    else p[i].tg=p[i].y/p[i].x;
}


sort(p+2,p+n+1,cmp);


/*
for(i=1;i<=n;i++)
    cout<<p[i].x+xmin<<' '<<p[i].y+ymin<<' '<<p[i].tg<<endl;


cout<<arie(p[1].x,p[1].y,p[3].x,p[3].y,p[2].x,p[2].y)<<endl;
cout<<arie(p[1].x,p[1].y,p[3].x,p[3].y,p[4].x,p[4].y)<<endl;
cout<<endl;
*/

int p1,p2,p3;
S.push(0);
S.push(1);
for(i=2;i<=n+1;i++)
{S.push(i);

    p1=S.top();S.pop();
    p2=S.top();S.pop();
    p3=S.top();
while(S.size()>1 && !arie(p[p3].x,p[p3].y,p[p2].x,p[p2].y,p[p1].x,p[p1].y))
{S.push(p1);
 p1=S.top();S.pop();
 p2=S.top();S.pop();
 p3=S.top();
}
S.push(p2);
S.push(p1);
}

fout<<S.size()-2<<endl;
/*
while(S.size()>1){
    p1=S.top();S.pop();
    cout<<p[p1].x+xmin<<' '<<p[p1].y+ymin<<'\n';

}*/
afisare();
}

void afisare(){
if(S.size()>2){
    int x=S.top();
    S.pop();
    afisare();
    fout<<setprecision(6)<<fixed<<p[x].x+xmin<<' '<<p[x].y+ymin<<'\n';
}

}