Pagini recente » Cod sursa (job #1727836) | Cod sursa (job #2719684) | Cod sursa (job #858405) | Cod sursa (job #760631) | Cod sursa (job #934150)
Cod sursa(job #934150)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define NMAX 120001
struct punct {
double x,y;
};
punct v[NMAX],s[NMAX];
inline double cross_product(punct a, punct b, punct c)
{
return (double)a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
inline bool cmp(const punct &a, const punct &b)
{
return cross_product(v[1],a,b)>0;
}
int graham(int n)
{
int i,p;
for(i=2;i<=n;i++)
if(v[1].y>v[i].y || (v[i].y==v[1].y && v[i].x<v[1].x))
swap(v[1],v[i]);
sort(v+2,v+n+1,cmp);
s[1]=v[1];
s[2]=v[2];
p=2;
for(i=3;i<=n;i++) {
while(p>=2 && cross_product(s[p-1],s[p],v[i])<0)
p--;
s[++p]=v[i];
}
return p;
}
int main ()
{
int n,i,p;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
f.close();
p=graham(n);
g<<p<<'\n';
g<<fixed;
for(i=1;i<=p;i++)
g<<setprecision(6)<<s[i].x<<" "<<s[i].y<<'\n';
g.close();
return 0;
}