Pagini recente » Cod sursa (job #264735) | Cod sursa (job #1771716) | Cod sursa (job #1606340) | Cod sursa (job #2826385) | Cod sursa (job #1409690)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
const int NMAX = 120005;
const double eps = 1e-12;
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct puncte
{
double x;
double y;
bool operator < (const puncte &t) const
{
if (t.x < x)
return true;
if (t.x > x)
return false;
if (t.y < y)
return true;
return false;
}
};
int N;
vector <puncte> punct;
bool viz[NMAX];
int stiva[NMAX],top;
double cross_product(puncte O, puncte A, puncte B)
{
return(A.x - O.x)*(B.y-O.y) - (B.x - O.x)*(A.y - O.y);
}
void solve(int pct)
{
while(top >= 2 && cross_product(punct[stiva[top-1]],punct[stiva[top]],punct[pct]) < eps)
{
viz[ stiva[top] ] = false;
top--;
}
top++;
stiva[top] = pct;
viz[ stiva[top] ] = true;
}
int main()
{
f >> N;
for (int i = 1; i <= N; ++i)
{
puncte pct;
f >> pct.x >> pct.y;
punct.push_back(pct);
}
sort(punct.begin(), punct.end());
stiva[1] = 0;
stiva[2] = 1;
top = 2;
viz[1] = 1;
for (int i = 2; i < punct.size(); ++i)
{
if (!viz[i])
solve(i);
}
for (int i = punct.size()-2; i >= 0; --i)
{
if(!viz[i])
solve(i);
}
g << top-1 << '\n';
for (int i = 1; i < top; ++i)
{
g << fixed << setprecision(12) << punct[stiva[i]].x << " " <<punct[stiva[i]].y << '\n';
}
f.close();
g.close();
return 0;
}