Pagini recente » Cod sursa (job #99413) | Cod sursa (job #2012750) | Cod sursa (job #2600482) | Cod sursa (job #2486137) | Cod sursa (job #2543791)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax = 120000, inf = 0x3f3f3f3f;
struct Point{
double x, y;
bool operator < (const Point &other){
if (x == other.x)
return y < other.y;
return x < other.x;
}
};
Point v[Nmax + 5], st[Nmax + 5];
Point p0;
int n, nr;
void Read(){
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
}
double Determinant(Point a, Point b, Point c){
double s1 = 0, s2 = 0;
s1 = b.x * c.y + a.x * b.y + c.x * a.y;
s2 = b.x * a.y + c.x * b.y + c.y * a.x;
return s1 - s2;
}
int Compare(Point a, Point b){
return Determinant(p0, a, b) > 0;
}
void Solve(){
p0.x = p0.y = inf;
int pos = 0;
for (int i = 1; i <= n; i++)
if (v[i] < p0){
p0 = v[i];
pos = i;
}
swap(v[pos], v[1]);
sort(v + 1, v + n + 1, Compare);
st[1] = v[1];
st[2] = v[2];
nr = 2;
for (int i = 3; i <= n; i++){
while (nr >= 2 && Determinant(st[nr - 1], st[nr], v[i]) < 0)
nr--;
st[++nr] = v[i];
}
}
void Print(){
fout << nr << '\n';
for (int i = 1; i <= nr; i++){
fout << fixed << setprecision(6) << st[i].x << ' ';
fout << fixed << setprecision(6) << st[i].y << '\n';
}
}
int main(){
Read();
Solve();
Print();
return 0;
}