Pagini recente » Cod sursa (job #1679671) | Cod sursa (job #631034) | Cod sursa (job #1206385) | Cod sursa (job #1616366) | Cod sursa (job #2270027)
#include <iostream>
#include <bits/stdc++.h>
#define pdd pair <double, double>
#define Nmax 120010
#define mp make_pair
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
pdd points[Nmax];
vector < pdd > L;
double orientation(pdd q,pdd p,pdd r)
{
return (r.second - q.second) * (p.first - q.first) - (r.first - q.first) * (p.second - q.second);
}
bool cmp(pdd a,pdd b)
{
return orientation(points[1],a,b) < 0;
}
void sortare()
{
int pr = 1;
for (int i = 2; i <= n; i++)
if (points[i] < points[pr])
pr = i;
swap(points[1],points[pr]);
sort(points + 2, points + n + 1, cmp);
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> points[i].first >> points[i].second;
/* for (int i = 1; i<=n; i++)
cout << points[i].first << " " << points[i].second << "\n";
cout << endl;*/
sortare();
/*for (int i = 1; i<=n; i++)
cout << points[i].first << " " << points[i].second << "\n";
cout << endl;*/
L.push_back(points[1]);
L.push_back(points[2]);
for (int i = 3; i <= n; i++)
{//cout << orientation(L[L.size()-2],L[L.size()-1],points[i]) << " " << points[i].first << " " << points[i].second << "\n";
while (L.size() > 2 && orientation(L[L.size()-2],L[L.size()-1],points[i]) >= 0)
L.pop_back();
L.push_back(points[i]);
/*for(auto a:L)
cout << a.first << ", " << a.second << "\n";
cout << "\n";*/
}
fout << L.size() << "\n";
for(auto a:L)
fout << a.first << " " << a.second << "\n";
return 0;
}