Pagini recente » Cod sursa (job #19021) | Cod sursa (job #1875522) | Cod sursa (job #339463) | Cod sursa (job #2898878) | Cod sursa (job #3228288)
#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 partition(Point puncte[], int low, int high)
{
Point pivot = puncte[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++)
{
if (orientare(puncte[0].x, puncte[0].y, puncte[j].x, puncte[j].y, pivot.x, pivot.y))
{
i++;
swap(puncte[i], puncte[j]);
}
}
swap(puncte[i + 1], puncte[high]);
return (i + 1);
}
void quickSort(Point puncte[], int low, int high)
{
if (low < high)
{
int pi = partition(puncte, low, high);
quickSort(puncte, low, pi - 1);
quickSort(puncte, pi + 1, high);
}
}
int main()
{
int nr_pct, i;
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]);
quickSort(puncte, 1, nr_pct - 1);
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;
}
for (int i = 0; i < k; i++)
fout << puncte[solutie[i]].x << " " << puncte[solutie[i]].y << endl;
return 0;
}