Pagini recente » Cod sursa (job #2258169) | Cod sursa (job #75376) | Cod sursa (job #411178) | Cod sursa (job #14819) | Cod sursa (job #1486021)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#define val 10e-12
using namespace std;
struct elem
{
double x, y;
};
vector<elem> v;
vector<long> rez;
int value_sort(const void* a, const void* b)
{
elem* pa = *(elem**)a;
elem* pb = *(elem**)b;
if (pb->y < pa->y)
return 1;
else if (pa->y < pb->y)
return -1;
return 0;
}
static bool MyDataSorter(const elem& lhs, const elem& rhs)
{
if (lhs.y < rhs.y)
return true;
else
if (lhs.y == rhs.y && lhs.x > rhs.x)
return true;
return false;
}
double determ(elem e1, elem e2, elem e3)
{
return ((e1.x*e2.y) + (e2.x*e3.y) + (e3.x*e1.y) - (e1.y*e2.x) - (e2.y*e3.x) - (e3.y*e1.x));
}
int main()
{
bool *use;
ifstream input("infasuratoare.in");
int n;
input >> n;
use = new bool[n];
elem *e;
for (int i = 0; i < n; i++)
{
e = new elem();
input >> e->x;
input >> e->y;
v.push_back(*e);
use[i] = false;
}
input.close();
sort(v.begin(), v.end(), MyDataSorter);
rez.push_back(0);
rez.push_back(1);
use[0] = use[1] = true;
for (int i = 2; i < v.size(); i++)
{
while (!use[i] && determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < val)
{
use[rez[rez.size() - 1]] = false;
rez.pop_back();
if (rez.size() < 2)
break;
}
use[i] = true;
rez.push_back(i);
}
for (int i = v.size(); i >= 0; i--)
{
while ((i == 1 || !use[i]) && determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < val)
{
use[rez[rez.size() - 1]] = false;
rez.pop_back();
if (rez.size() < 2)
break;
}
if (!use[i])
{
rez.push_back(i);
use[i] = true;
}
}
ofstream output("infasuratoare.out");
output << rez.size() << endl;
for (int i = 0; i < rez.size(); i++)
output << setprecision(9) << fixed << v[rez[i]].x << " " << v[rez[i]].y << endl;
output.close();
return 0;
}