Pagini recente » Cod sursa (job #605933) | Cod sursa (job #2405666) | Cod sursa (job #2321018) | Cod sursa (job #29799) | Cod sursa (job #2168061)
#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[i])<=0) k--;
H[++k]=v[i];
}
int kk=k+1;
for(i=n;i>=1;i--)
{
while(k>=kk && semn(H[k-1],H[k],v[i])<=0) k--;
H[++k]=v[i];
}
k--;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
hull();
g<<k<<"\n";
for(i=1;i<=k;i++)
g<<fixed<<setprecision(12)<<H[i].x<<" "<<H[i].y<<"\n";
f.close();
g.close();
return 0;
}