Pagini recente » Cod sursa (job #1815253) | Cod sursa (job #277967) | Cod sursa (job #2938119) | Cod sursa (job #519660) | Cod sursa (job #791083)
Cod sursa(job #791083)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 0x3f3f3f3f
#define MAX 131072
#define EPS 1e-12
using namespace std;
struct punct
{
double x, y;
}p[MAX];
int pct, stk[MAX], ind[MAX], n;
double abs(double a)
{
if(a > 0) return a;
return -a;
}
bool LESS(double a, double b)
{
return a + EPS < b;
}
bool EQUAL(double a, double b)
{
return abs(a - b) < EPS;
}
bool cmp(int a, int b)
{
return LESS((p[a].x - p[pct].x) * (p[b].y - p[pct].y), (p[b].x - p[pct].x) * (p[a].y - p[pct].y));
}
bool semn(int i1, int i2, int i3)
{
return (p[i1].x * p[i2].y + p[i2].x * p[i3].y + p[i1].y * p[i3].x - p[i2].y * p[i3].x - p[i1].y * p[i2].x - p[i3].y * p[i1].x) > EPS;
}
int main()
{
ifstream in("infasuratoare.in");
in>>n;
p[0].x = p[0].y = INF;
for(int i = 1; i <= n; i++)
{
in>>p[i].x>>p[i].y;
if(LESS(p[i].x, p[pct].x) || (EQUAL(p[i].x, p[i].y) && LESS(p[i].y, p[pct].y))) pct = i;
}
in.close();
for(int i = 1; i <= n; i++)
if(i != pct) ind[++ind[0]] = i;
sort(ind + 1, ind + ind[0] + 1, cmp);
stk[stk[0] = 1] = pct;
for(int i = 1; i <= ind[0]; i++)
{
while(stk[0] >= 2 && semn(stk[stk[0] - 1], stk[stk[0]], ind[i])) stk[0]--;
stk[++stk[0]] = ind[i];
}
stk[++stk[0]] = pct;
ofstream out("infasuratoare.out");
out<<stk[0] - 1<<"\n";
for(int i = stk[0]; i > 1; i--)
out<<fixed<<setprecision(6)<<p[stk[i]].x<<" "<<p[stk[i]].y<<"\n";
out.close();
return 0;
}