Pagini recente » Cod sursa (job #2923118) | Cod sursa (job #2084555) | Cod sursa (job #2194513) | Cod sursa (job #2174369) | Cod sursa (job #2820693)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
/// Convex HULL
struct Punct
{
double x, y;
bool operator < (const Punct alt) const
{
if(alt.y==y)
return x<alt.x;
return y<alt.y;
}
};
Punct a[120003];
int n;
bool viz[120005];
int st[120005],top;
/// ret. + daca C se afla in semiplanul +
/// determinat de dreapta (A,B)
double f(Punct A, Punct B, Punct C)
{
return (A.y - B.y)*C.x + (B.x - A.x) * C.y
+ A.x * B.y - A.y * B.x;
}
void citire()
{
fin>>n;
int i;
for(i=1; i<=n; i++)
fin>>a[i].x>>a[i].y;
}
void ConvexHull()
{
sort(a+1,a+n+1);
st[++top]=1;
st[++top]=2;
viz[2]=1;
for(int i=3; i<=n; i++)
{
while(f(a[st[top-1]],a[st[top]],a[i])<0)
{
viz[st[top]]=0;
top--;
}
st[++top]=i;
viz[i]=1;
}
for(int i=n; i>=1; i--)
{
if(!viz[i])
{
while(f(a[st[top-1]],a[st[top]],a[i])<0)
top--;
st[++top]=i;
}
}
fout<<top-1<<"\n";
for(int i=1; i<top; i++)
fout<<setprecision(12)<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
}
int main()
{
/*
Punct A, B, C;
A.x = A.y = 0;
B.x = B.y = 5;
C.x = 1; C.y = 6;
cout << F(A,B,C);
*/
citire();
ConvexHull();
return 0;
}