Pagini recente » Cod sursa (job #755707) | Cod sursa (job #2259332) | Cod sursa (job #899589) | Cod sursa (job #774445) | Cod sursa (job #1765761)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int nmax = 120005;
const double eps = 0.000000000001;
int N,st[nmax],fr[nmax],top;
struct Pct
{
double x,y;
bool operator < (const Pct &A) const
{
return y < A.y;
}
};
Pct v[nmax];
inline double Prod(Pct A, Pct B, Pct C)
{
return C.x*(B.y - A.y) + C.y*(A.x - B.x) + A.y*(B.x - A.x) - A.x*(B.y - A.y);
}
int main()
{
int i,semn;
fin >> N;
for(i = 1; i <= N; i++)
fin >> v[i].x >> v[i].y;
sort(v+1,v+N+1);
top = 2;
st[1] = 1, st[2] = 2;
fr[2] = semn = 1;
for(i = 3; i; i+=semn)
{
while(top >= 2 && Prod(v[st[top-1]],v[st[top]],v[i]) <= eps)
{
fr[top]--;
top--;
}
st[++top] = i;
fr[top]++;
if(i == N) semn = -1;
}
top--;
fout << top << "\n";
for(i = 1; i <= top; i++) fout << v[st[i]].x << " " << v[st[i]].y << "\n";
fout.close();
return 0;
}