Pagini recente » Cod sursa (job #203424) | Monitorul de evaluare | Cod sursa (job #1770145) | Cod sursa (job #2014299) | Cod sursa (job #1773368)
#include <fstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define pi 3.1415926535897
using namespace std;
ofstream g("infasuratoare.out");
long n, sav;
struct point{
double x, y;
}H[120005];
vector<point> st;
double unghi(point A)
{
double a;
if (A.x >= st[0].x && A.y >= st[0].y)
a = atan((A.x - st[0].x)/(A.y - st[0].y));
else if (A.x >= st[0].x && A.y <= st[0].y)
a = pi - atan((A.x - st[0].x)/(st[0].y - A.y));
else if (A.x <= st[0].x && A.y <= st[0].y)
a = atan((st[0].x - A.x)/(st[0].y - A.y)) + pi;
else
a = 2*pi - atan((st[0].x - A.x)/(A.y - st[0].y));
return a;
}
bool comp(point A, point B)
{
double a = unghi(A);
double b = unghi(B);
return a<b;
}
double ecd(point A,point B,point C)
{
return (C.x-A.x)*(B.y-A.y) - (C.y-A.y)*(B.x-A.x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
scanf("%ld",&n);
sav = 1;
for (int i = 1; i <= n; i++)
{
scanf("%lf%lf", &H[i].x, &H[i].y);
if (H[i].x < H[sav].x)
sav = i;
}
st.push_back(H[sav]);
for (int i = sav; i <= n; i++)
H[i] = H[i+1];
n--;
sort(H+1, H+n+1, comp);
for (int i = 1; i <= n; i++)
{
while (ecd(st[st.size()-2],st[st.size()-1],H[i])<1)
st.pop_back();
st.push_back(H[i]);
}
g<<fixed;
g<<st.size()<<'\n';
g<<setprecision(6);
for (int i = st.size()-1; i >= 0; i--)
g<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}