Pagini recente » Cod sursa (job #818597) | Cod sursa (job #77878) | Cod sursa (job #2614646) | Cod sursa (job #104455) | Cod sursa (job #3228286)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point
{
double x, y;
};
int orientare(double x1, double y1, double x2, double y2, double x3, double y3)
{
double d = (y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1);
return d < 0;
}
int main()
{
int nr_pct, i, j;
fin >> nr_pct;
Point puncte[120000];
for (i = 0; i < nr_pct; i++)
fin >> puncte[i].x >> puncte[i].y;
int pct_initial = 0;
for (i = 1; i < nr_pct; i++)
if (puncte[i].x < puncte[pct_initial].x) pct_initial = i;
else if(puncte[i].x == puncte[pct_initial].x && puncte[i].y < puncte[pct_initial].y) pct_initial = i;
swap(puncte[0], puncte[pct_initial]);
for (i = 1; i < nr_pct; i++)
for (j = i + 1; j < nr_pct; j++)
if (orientare(puncte[0].x, puncte[0].y, puncte[i].x, puncte[i].y, puncte[j].x, puncte[j].y))
swap(puncte[i], puncte[j]);
int solutie[120000], k;
solutie[0] = 0;
solutie[1] = 1;
k = 2;
for(i = 2; i<nr_pct; i++)
{
while(k>2 && orientare(puncte[solutie[k-2]].x, puncte[solutie[k-2]].y, puncte[solutie[k-1]].x, puncte[solutie[k-1]].y, puncte[i].x, puncte[i].y))
k--;
solutie[k++] = i;
}
fout<<k<<endl;
for (int i = 0; i < k; i++)
fout << puncte[solutie[i]].x << " " << puncte[solutie[i]].y << endl;
return 0;
}