Pagini recente » Cod sursa (job #2687801) | Cod sursa (job #3171182) | Cod sursa (job #1616789) | Cod sursa (job #2552520) | Cod sursa (job #2116230)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define lim 120010
struct pct {double x,y;} ini[lim];
int sol[lim];
int minm(1), n, dr;
double det (pct A, pct B, pct C)
{
double rez = A.x*B.y + B.x*C.y + A.y*C.x - C.x*B.y - B.x*A.y - A.x*C.y;
return rez;
}
bool cmp (pct A, pct B)
{
return det (ini[1], A, B) >= 0;
}
int main()
{
fin>>n;
for (int i=1; i<=n; i++)
{
fin>>ini[i].x>>ini[i].y;
if (ini[i].x < ini[minm].x) minm=i;
else if (ini[i].x==ini[minm].x && ini[i].y<ini[minm].y) minm=i;
}
swap (ini[1], ini[minm]);
sort (ini+2, ini+n+1, cmp);
dr=0;
for (int i=1; i<=n; i++)
{
while (dr>1 && det(ini[sol[dr-1]], ini[sol[dr]], ini[i]) < 0) dr--;
sol[++dr]=i;
}
fout<<dr<<'\n';
for (int i=1; i<=dr; i++)
fout<<fixed<<ini[sol[i]].x<<' '<<ini[sol[i]].y<<'\n';
return 0;
}