Pagini recente » Cod sursa (job #1004989) | Cod sursa (job #707931) | Rating Vlase Paul (vlase.paul) | Cod sursa (job #1818247) | Cod sursa (job #2836053)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120000;
int N;
struct elem
{
long double x, y;
};
elem punct[NMAX + 5];
elem stiva[NMAX + 5];
int cntStiva;
long double determinant(elem a, elem b, elem c)
{
return (a.x * b.y - a.y * b.x) + (b.x * c.y - b.y * c.x) + (c.x * a.y - a.x * c.y);
}
bool verifica(elem a, elem b, elem c)
{
return (determinant(a, b, c) > 0);
}
bool cmp(elem &a, elem &b)
{
return verifica(punct[1], a, b);
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i ++)
{
fin >> punct[i].x >> punct[i].y;
}
for(int i = 2; i <= N; i ++)
{
if(punct[i].x < punct[1].x)
{
swap(punct[i], punct[1]);
}
else
{
if(punct[i].x == punct[i].x)
{
if(punct[i].y < punct[i].y)
{
swap(punct[i], punct[1]);
}
}
}
}
sort(punct + 2, punct + N + 1, cmp);
stiva[++cntStiva] = punct[1];
for(int i = 2; i <= N; i ++)
{
while(cntStiva >= 2 && verifica(stiva[cntStiva - 1], stiva[cntStiva], punct[i]) == false)
{
cntStiva--;
}
stiva[++cntStiva] = punct[i];
}
fout << cntStiva << '\n';
for(int i = 1; i <= cntStiva; i ++)
{
fout << fixed << setprecision(12) << stiva[i].x << ' ';
fout << fixed << setprecision(12) << stiva[i].y << ' ';
fout << '\n';
}
return 0;
}