Pagini recente » Cod sursa (job #2616436) | Cod sursa (job #2647658) | Cod sursa (job #695845) | Cod sursa (job #3224090) | Cod sursa (job #2351242)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
int n,i,k;
struct punct
{
double x,y;
};
punct v[120005],H[120005];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bool cmp(punct a,punct b)
{
if(a.x<b.x) return 1;
if(a.x==b.x && a.y<b.y) return 1;
return 0;
}
double semn(punct A,punct B,punct O)
{
return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);
}
void hull()
{
for(i=1;i<=n;i++)
{
while(k>=2 && semn(H[k-1],H[k],v)<=0) k--;
H[++k]=v;
}
int kk=k+1;
for(i=n;i>=1;i--)
{
while(k>=kk && semn(H[k-1],H[k],v)<=0) k--;
H[++k]=v;
}
k--;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>v.x>>v.y;
sort(v+1,v+n+1,cmp);
hull();
g<<k<<"\n";
for(i=1;i<=k;i++)
g<<fixed<<setprecision(12)<<H.x<<" "<<H.y<<"\n";
f.close();
g.close();
return 0;
}