Pagini recente » Cod sursa (job #2633455) | Cod sursa (job #1376150) | Cod sursa (job #506884) | Cod sursa (job #2333393) | Cod sursa (job #1392169)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define DMAX 120008
ifstream fin(IN);
ofstream fout(OUT);
struct punct {double x, y;};
int n;
punct st[DMAX];//stiva
int nst;//dim stiva
punct v[DMAX];
void citire();
int det(punct a, punct b, punct c);
bool sortare(const punct &a, const punct &b);
void inf();
void afisare();
int main(){
citire();
inf();
afisare();
return 0;
}
void afisare(){
int i;
fout <<nst<<'\n';
for (i=1; i<=nst; ++i)
fout <<fixed<<setprecision(6)<<st[i].x<<' '<<st[i].y<<'\n';
fout.close();
}
void inf(){
sort(v+2, v+n+1, sortare);
st[++nst]=v[1];
st[++nst]=v[2];
int i;
for (i=3; i<=n; ++i){
//si daca det < 0 atunci nu e bine si scot ultimele doua
while (det(st[nst-1], st[nst], v[i])<=0 && nst>1)
--nst;
st[++nst]=v[i];
}
}
bool sortare(const punct &a, const punct &b){
return det(v[1], a, b)>0;
}
int det(punct a, punct b, punct c){
return a.x*b.y+b.x*c.y+c.x*a.y-(c.x*b.y+a.x*c.y+b.x*a.y);
}
void citire(){
fin >>n;
int i;
for (i=1; i<=n; ++i)
fin >>v[i].x>>v[i].y;
int mi=1;
for (i=2; i<=n; ++i)
if ((v[i].x < v[mi].x) || (v[i].x==v[mi].x && v[i].y<v[mi].y))
mi=i;
punct aux=v[1];
v[1]=v[mi];
v[mi]=aux;
}