Pagini recente » Cod sursa (job #22162) | Cod sursa (job #1534859) | Cod sursa (job #1052269) | Cod sursa (job #305009) | Cod sursa (job #1295753)
#include <fstream>
#define nmax 120010
#define x first
#define y second
#include <algorithm>
#include <iomanip>
using namespace std;
long long n;
typedef pair<double,double> point;
point v[nmax];
point stk[nmax];
inline double slope(point x,point y,point c){
return (y.x - x.x)*(c.y - x.y) - (y.y - x.y)*(c.x - x.x);
}
inline bool cmp(point x1,point x2){
return slope(v[1],x1,x2) < 0;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
void read(){
fin>>n;
for(long i = 1;i <= n;i++){
fin>>v[i].x>>v[i].y;
}
}
void convex_hull(){
int ps = 1;
for(long i = 2;i <= n;i++)
if(v[i]<v[ps])
ps = i;
swap(v[ps],v[1]);
sort(v+2,v+n+1,cmp);
stk[1] = v[1];
stk[2] = v[2];
int ms = 2;
for(long i = 3;i <= n;i++){
while(ms >= 2 && slope(stk[ms-1],stk[ms],v[i]) > 0)--ms;
stk[++ms] = v[i];
}
fout<<fixed;
fout<<ms<<"\n";
for(ms;ms;ms--)fout<<setprecision(9)<<stk[ms].x<<" "<<stk[ms].y<<"\n";
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
read();
convex_hull();
return 0;
}