Pagini recente » Cod sursa (job #1600734) | Cod sursa (job #1620313) | Cod sursa (job #1022987) | Cod sursa (job #2395886) | Cod sursa (job #345184)
Cod sursa(job #345184)
#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <algorithm>
#define INPUT_F "infasuratoare.in"
#define OUTPUT_F "infasuratoare.out"
using namespace std;
#define EPS 1E-12
#define MAX_N 10000
typedef pair<double, double> Point;
typedef vector<Point> PV;
#define x first
#define y second
PV a;
inline double abs(double x) { if (x < 0) return -x; return x; }
bool isLeftTurn(Point a, Point b, Point c)
{
double r = (c.x - a.x)*(b.y - a.y) - (c.y - a.y)*(b.x - a.x);
if (abs(r) < EPS)
return (c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y) <
(b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
if (r < 0)
return true;
return false;
}
struct PolarCompare
{
PolarCompare(const Point &b)
{
this->base = b;
}
bool operator ()(const Point &a, const Point &b)
{
return isLeftTurn(base, a, b);
}
Point base;
};
void read_data(istream &in)
{
int N;
double x, y;
in >> N;
for (int i = 0; i < N; ++i)
{
in >> x >> y;
a.push_back(Point(x, y));
}
}
void print_data(ostream &out, const PV &v)
{
out << v.size() << endl;
out.flags(ios::fixed);
for (PV::const_iterator i = v.begin(); i != v.end(); i++)
out << setprecision(6) << i->x << " " << i->y << endl;
}
// very inefficient design/implementation all for the sake of clarity
PV solve(PV &a)
{
swap(a[0], *min_element(a.begin(), a.end()));
sort(a.begin() + 1, a.end(), PolarCompare(a[0]));
//print_data(cout, a);
//int x;
//cin >> x;
vector<Point> result;
result.push_back(a[0]);
result.push_back(a[1]);
for (PV::iterator i = a.begin() + 2; i != a.end(); i++)
{
while (!isLeftTurn(result.end()[-2], result.end()[-1], *i))
result.pop_back();
result.push_back(*i);
}
//sort(result.begin(), result.end(), PolarCompare(Point(0, 0)));
return result;
}
int main()
{
ifstream fin(INPUT_F);
ofstream fout(OUTPUT_F);
read_data(fin);
//print_data(cout, a);
print_data(fout, solve(a));
fin.close();
fout.close();
return 0;
}