Pagini recente » Cod sursa (job #519570) | Cod sursa (job #991747) | untitled1 | Cod sursa (job #2810280) | Cod sursa (job #1485989)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct elem
{
double x, y;
};
vector<elem> v;
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) - (e3.x * e2.y) - (e2.x * e1.y) - (e3.y * e1.x));
}
int main()
{
vector<long> rez;
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);
rez.push_back(2);
use[0] = use[1] = use[2] = true;
for (int i = 3; i < v.size(); i++)
{
bool ok = false;
while (rez.size() > 2)
{
if (determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < 0)
{
ok = true;
use[rez[rez.size()-1]] = false;
rez.pop_back();
}
else
{
ok = true;
break;
}
}
if (ok)
{
use[i] = true;
rez.push_back(i);
}
}
for (int i = v.size() - 2; i >= 2; i--)
{
if (!use[i])
{
bool ok = false;
while (rez.size() > 2)
{
if (determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < 0)
{
ok = true;
use[rez[rez.size() - 1]] = false;
rez.pop_back();
}
else
{
ok = true;
break;
}
}
if (ok)
rez.push_back(i);
}
}
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;
}