Pagini recente » Cod sursa (job #3356217) | Cod sursa (job #1395236) | Cod sursa (job #2238729) | Cod sursa (job #3302992) | Cod sursa (job #3316720)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct a
{
double x,y;
int loc;
}v[120001];
int cmp(a A , a B)
{
return A.x < B.x;
}
int linie (a A , a B , a C)
{
return A.x * B.y + B.x * C.y + C.x * A.y - B.y * C.x - C.y * A.x - A.y * B.x;
}
int st[120001];
int main()
{
int n;
cin >>n;
for (int i = 1; i <= n; i++)
{
cin >>v[i].x>>v[i].y;
}
sort (v + 1 , v + n + 1 , cmp);
for (int i = 2; i < n; i++)
{
///loc = 1 ==> sub sau loc = 2 ==> peste
if (linie(v[1] , v[i] , v[n]) < 0)
{
v[i].loc = 1;
}
else
{
v[i].loc = 2;
}
}
st[1] = 1;
int k = 1;
for (int i = 2; i <= n; i++)
{
if (v[i].loc == 1 || v[i].loc == 0)
{
while (k > 1 && linie(v[st[k - 1]], v[st[k]] , v[i]) > 0)
{
k--;
}
k++;
st[k] = i;
}
}
int c = k;
st[k] = n;
for (int i = n - 1; i >= 1; i--)
{
if (v[i].loc == 2 || v[i].loc == 0)
{
while (k > c && linie(v[st[k - 1]] , v[st[k]] , v[i]) > 0)
{
k--;
}
k++;
st[k] = i;
}
}
cout <<k - 1<<"\n";
for (int i = k - 1; i >= 1; i--)
{
cout <<v[st[i]].x<<".000000 "<<v[st[i]].y<<".000000\n";
}
return 0;
}