Pagini recente » Cod sursa (job #1049068) | Cod sursa (job #1768129) | Cod sursa (job #2674552) | Cod sursa (job #2634446) | Cod sursa (job #2685004)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int MAXN = 120004;
struct Punct
{
long double x{0}, y{0};
bool operator<(Punct term)
{
return x < term.x || (!(x < term.x) && y < term.y);
}
};
int n;
Punct a[MAXN];
vector<Punct> s;
long double det(Punct a, Punct b, Punct c)
{
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
bool cmp(Punct x1, Punct x2)
{
return det(a[0], x1, x2) < 0;
}
int main()
{
fin >> n;
for(int i = 0; i < n; i++)
fin >> a[i].x >> a[i].y;
int pos = 0;
for(int i = 1; i < n; i++)
if(a[i] < a[pos])
pos = i;
swap(a[0], a[pos]);
sort(a+1, a+n, cmp);
s.push_back(a[0]);
s.push_back(a[1]);
for(int i = 2; i < n; i++)
{
while(s.size() > 1 && det(s[s.size()-2], s[s.size()-1], a[i]) > 0) s.pop_back();
s.push_back(a[i]);
}
fout << s.size() << "\n";
for(int i = s.size()-1; i >= 0; i--)
fout <<setprecision(15)<< s[i].x << " " << s[i].y << "\n";
return 0;
}