Pagini recente » Cod sursa (job #518017) | Cod sursa (job #2459493) | Cod sursa (job #2530970) | Cod sursa (job #2411347) | Cod sursa (job #3300637)
#include <bits/stdc++.h>
using namespace std;
#define MAX 150005
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, stiva[MAX], top, indice_start;
long double xmin, ymin = 1e18L;
struct Punct {
long double x, y;
} puncte[MAX];
bool comp(const Punct &a, const Punct &b) {
return a.x * b.y >= b.x * a.y;
}
bool convex(Punct a, Punct b, Punct c) {
long double r = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
return r > 0;
}
void citire(){
fin >> n;
for (int i = 0; i < n; i ++)
{
fin >> puncte[i].x >> puncte[i].y;
if ((puncte[i].y < ymin) || (puncte[i].y == ymin && puncte[i].x < xmin))
{
ymin = puncte[i].y;
xmin = puncte[i].x;
indice_start = i;
}
}
for (int i = 0; i < n; i ++)
{
puncte[i].x = puncte[i].x - xmin;
puncte[i].y = puncte[i].y - ymin;
}
}
void construieste_Infasuratoare() {
swap(puncte[0], puncte[indice_start]);
sort(puncte + 1, puncte + n, comp);
stiva[top++] = 0;
stiva[top++] = 1;
for (int i = 2; i < n; i++)
{
while ((top >= 2) && (!convex(puncte[stiva[top - 2]], puncte[stiva[top - 1]], puncte[i]))) {
top--;
}
stiva[top++] = i;
}
}
void scrie_rez() {
fout << top << "\n";
fout << fixed << setprecision(10);
for (int i = 0; i < top; i ++)
{
fout << puncte[stiva[i]].x + xmin << " " << puncte[stiva[i]].y + ymin << "\n";
}
}
int main() {
citire();
construieste_Infasuratoare();
scrie_rez();
return 0;
}