Pagini recente » Cod sursa (job #999554) | Cod sursa (job #1037899) | Cod sursa (job #2127718) | Cod sursa (job #34818) | Cod sursa (job #1051243)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define MAX_N 120001
using namespace std;
typedef pair<double, double> punct;
punct v[MAX_N];
punct stiva[MAX_N];
int n,head;
double prod(const punct& a, const punct& b, const punct& c){
return (b.first-a.first)*(c.second-a.second)-(b.second-a.second)*(c.first-a.first);
}
int cmp(const punct& p1, const punct& p2){
return prod(v[1],p1,p2)<0;
}
int main()
{
int i;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(i=1;i<=n;i++){
f>>v[i].first>>v[i].second;
}
//sorteaza puncte
int pos=1;
for(i=2;i<=n;i++)
if(v[i]<v[pos])
pos=i;
swap(v[1],v[pos]);
sort(v+2,v+n+1,cmp);
/*for(i=1;i<=n;i++){
cout<<v[i].first<<" "<<v[i].second<<'\n';
}*/
stiva[1]=v[1];
stiva[2]=v[2];
head=2;
for(i=3;i<=n;i++){
while(head>=2 && prod(stiva[head-1],stiva[head],v[i])>0)
head--;
stiva[++head]=v[i];
}
g<<fixed;
g<<head<<'\n';
for(i=head;i>=1;i--)
g<<setprecision(12)<<stiva[i].first<<" "<<stiva[i].second<<'\n';
return 0;
}