Pagini recente » Cod sursa (job #89957) | Cod sursa (job #2824737) | Cod sursa (job #1433233) | Cod sursa (job #2095657) | Cod sursa (job #1773402)
#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,int &cadran)
{
double a;
if (A.x >= st[0].x && A.y >= st[0].y)
a = (A.x - st[0].x)/(A.y - st[0].y),cadran = 1;
else if (A.x >= st[0].x && A.y <= st[0].y)
a = -(A.x - st[0].x)/(st[0].y - A.y),cadran = 2;
else if (A.x <= st[0].x && A.y <= st[0].y)
a = (st[0].x - A.x)/(st[0].y - A.y),cadran = 3;
else
a = -(st[0].x - A.x)/(A.y - st[0].y),cadran = 4;
return a;
}
bool comp(point A, point B)
{
int cadranA,cadranB;
double a = unghi(A,cadranA);
double b = unghi(B,cadranB);
if (cadranA == cadranB)
return a<b;
return cadranA<cadranB;
}
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;
}