Pagini recente » Cod sursa (job #1997670) | Cod sursa (job #1713479) | Cod sursa (job #1756938) | Cod sursa (job #571112) | Cod sursa (job #1844379)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define VAL 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x;
double y;
};
punct P[VAL];
punct sol[VAL];
int N, i, j, M;
int st[VAL], top;
bool ok[VAL];
bool cmp(punct a, punct b)
{
if (a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
bool trig(punct a, punct b)
{
return (a.y / a.x)<(b.y / b.x);
}
double AREA(punct a, punct b, punct c)
{
double S;
S=a.x*b.y+b.x*c.y+c.x*a.y;
S-=a.x*c.y+b.x*a.y+c.x*b.y;
return S;
}
int main()
{
fin >> N;
for (i=1; i<=N; i++)
fin >> P[i].x >> P[i].y;
sort(P+1, P+N+1, cmp);
st[1]=1;
st[2]=2;
top=2;
for (i=3; i<=N; i++)
{
while (top!=1 && AREA(P[st[top]], P[st[top-1]], P[i])<0)
top--;
st[++top]=i;
}
while (top!=0)
ok[st[top--]]=true;
st[1]=1;
st[2]=2;
top=2;
for (i=3; i<=N; i++)
{
while (top!=1 && AREA(P[st[top]], P[st[top-1]], P[i])>=0)
top--;
st[++top]=i;
}
while (top!=0)
ok[st[top--]]=true;
for (i=1; i<=N; i++)
if (ok[i]==true)
sol[++M]=P[i];
fout << M << '\n';
sort(sol+1, sol+M+1, trig);
for (i=1; i<=M; i++)
{
fout << fixed << setprecision(12) << sol[i].x << " ";
fout << fixed << setprecision(12) << sol[i].y << '\n';
}
fin.close();
fout.close();
return 0;
}