Pagini recente » Cod sursa (job #259936) | Cod sursa (job #297317) | Cod sursa (job #1897668) | Cod sursa (job #702864) | Cod sursa (job #3159140)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
vector<pair<float, float>>x;
bool valid(pair<float, float>a, pair<float, float>b)
{
if (a.first < b.first)
return true;
else if (a.first > b.first)
return false;
else if (a.second < b.second)
return true;
else return false;
}
enum Orientare {
TRIGONOMETRIC,
ORAR,
COLIN
};
Orientare calcOrientare(float x1, float y1, float x2, float y2, float x3, float y3)
{
double det = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
if (det > 0)
return TRIGONOMETRIC;
else if (det < 0)
return ORAR;
else
return COLIN;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
pair<float, float>p;
cin >> p.first >> p.second;
x.push_back(p);
}
sort(x.begin(), x.end(), valid);
vector<pair<float, float>>y=x;
int k = 0;
//y.push_back(x[0]);
while (k < x.size() - 2)
{
if (calcOrientare(x[k].first, x[k].second, x[k + 2].first, x[k + 2].second, x[k + 1].first, x[k + 1].second) == ORAR)
{
//y.push_back(x[k + 1]);
x.erase(x.begin() + k + 1);
}
else
k++;
}
k = 0;
while (k < y.size() - 2)
{
if (calcOrientare(y[k].first, y[k].second, y[k + 2].first, y[k + 2].second, y[k + 1].first, y[k + 1].second) == TRIGONOMETRIC)
y.erase(y.begin() + k + 1);
else
k++;
}
//y.push_back(x[x.size() - 1]);
cout << x.size() + y.size() - 2 << '\n';
for (int i = 1; i <y.size()-1; i++)
cout << y[i].first << ' ' << y[i].second << '\n';
cout << '\n' << '\n';
for (int i = x.size()-1; i >= 0; i--)
cout << x[i].first << ' ' << x[i].second << '\n';
/*for (int i = 0; i < n; i++, cout << '\n')
{
cout << x[i].first << ' ' << x[i].second;
}*/
return 0;
}