Pagini recente » Cod sursa (job #3238827) | Borderou de evaluare (job #2292016) | Cod sursa (job #2572505) | Cod sursa (job #2310523) | Cod sursa (job #1946710)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 120009;
#define point pair < double , double >
point p[nmax] , up[nmax] , low[nmax];
int n , i , upS , lowS;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
bool cmp1(point A , point B)
{
return A < B;
}
bool cmp2(point A , point B)
{
return A > B;
}
void readData()
{
fin >> n;
for (i = 1 ; i <= n ; ++i)
fin >> p[i].first >> p[i].second;
}
void upperEnvelope()
{
sort(p + 1 , p + n + 1 , cmp1);
for (i = 1 ; i <= n ; ++i)
{
while (2 <= upS)
{
point A = up[upS - 1];
point B = up[upS];
point C = p[i];
if ((A.second - B.second) * (A.first - C.first) <= (A.second - C.second) * (A.first - B.first))
upS--;
else break;
}
up[++upS] = p[i];
}
}
void lowerEnvelope()
{
sort(p + 1 , p + n + 1 , cmp2);
for (i = 1 ; i <= n ; ++i)
{
while (2 <= lowS)
{
point A = low[lowS - 1];
point B = low[lowS];
point C = p[i];
if ((A.second - B.second) * (A.first - C.first) <= (A.second - C.second) * (A.first - B.first))
lowS--;
else break;
}
low[++lowS] = p[i];
}
}
int main()
{
readData();
upperEnvelope();
lowerEnvelope();
fout << upS + lowS - 2 << '\n';
for (i = upS ; i ; --i)
{
fout << fixed << setprecision(10) << up[i].first << " ";
fout << fixed << setprecision(10) << up[i].second << '\n';
}
for (i = lowS - 1 ; 2 <= i ; --i)
{
fout << fixed << setprecision(10) << low[i].first << " ";
fout << fixed << setprecision(10) << low[i].second << '\n';
}
return 0;
}