Pagini recente » Cod sursa (job #552746) | Cod sursa (job #460074) | Cod sursa (job #147037) | Cod sursa (job #312569) | Cod sursa (job #3288345)
#include <fstream>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define oo 1000000000
struct punct
{
double x;
double y;
} v[120005];
bool smaller(punct x, punct y)
{
if (x.x < y.x)
{
return true;
}
if (x.x == y.x)
{
return x.y < y.y;
}
return false;
}
double distance(punct a, punct b)
{
return sqrt((b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}
int orientation(punct a, punct b, punct c)
{
// diferenta dintre panta dreptelor
// c.y-b.y/c.x-b.x - b.y-a.y/b.x-a.x
int d = (c.y - b.y) * (b.x - a.x) - (b.y - a.y) * (c.x - b.x);
if (d > 0)
return 1;
if (d < 0)
return -1;
// d==0
return 0;
}
int main()
{
cout << orientation({0, 0}, {1, 1}, {2, 3});
// punct a = {0, 0}, b = {1, -1};
// cout << atan2(b.y - a.y, b.x - a.x) / 3.14 * 180;
// return 0;
int n;
fin >> n;
punct start;
int istart;
vector<int> ras;
start.x = oo;
start.y = oo;
for (int i = 0; i < n; i++)
{
fin >> v[i].x >> v[i].y;
if (smaller(v[i], start))
{
start = v[i];
istart = i;
}
}
bool first = true;
int cur = istart;
cout << cur;
while (first || istart != cur)
{
first = false;
cout << cur << '\n';
ras.push_back(cur);
int nextPoint = cur;
for (int i = 0; i < n; i++)
{
if (i == cur)
{
continue;
}
int o = orientation(v[cur], v[nextPoint], v[i]);
// cout << o << " ";
if (o == 1)
{
nextPoint = i;
}
}
cur = nextPoint;
}
reverse(ras.begin(), ras.end());
fout << ras.size() << '\n';
for (auto i : ras)
{
fout << v[i].x << " " << v[i].y << '\n';
}
return 0;
}