Pagini recente » Cod sursa (job #1216229) | Cod sursa (job #937097) | Cod sursa (job #1633520) | Cod sursa (job #619854) | Cod sursa (job #1453454)
#define nmax 120005
#define eps 1e-12
#include <algorithm>
#define x first
#define y second
#include <fstream>
#include <iomanip>
using namespace std;
typedef pair<double,double> punct;
punct v[nmax];
int n,h;
int st[nmax];
bool vs[nmax];
void citeste(){
ifstream fin("infasuratoare.in");
fin>>n;
int i=1;
while(i<=n){
fin>>v[i].x>>v[i].y;
i++;
}
sort(v+1,v+n+1);
}
double cross_product(punct a,punct b,punct c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
void infasuratoare_convexa(){
h=2;
st[1]=1;
st[2]=2;
vs[2] = true;
for(int i=1,p=1;i>0;i+=(p=(i==n ? -p:p))){
if(vs[i])continue;
while(h>=2 && cross_product(v[st[h-1]],v[st[h]],v[i])<eps)vs[st[h--]]=0;
st[++h] = i;
vs[i] = 1;
}
ofstream fout("infasuratoare.out");
fout<<h-1<<"\n";
fout << setprecision(6)<<fixed;
for(int i=1;i<h;++i)fout<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
int main(){
citeste();
infasuratoare_convexa();
return 0;
}