Pagini recente » Cod sursa (job #2927009) | Cod sursa (job #3040519) | Cod sursa (job #1440436) | Cod sursa (job #2030859) | Cod sursa (job #2188641)
#include <bits/stdc++.h>
#define ld long double
using namespace std;
ofstream fout("infasuratoare.out");
ifstream fin("infasuratoare.in");
struct Point{
ld x;
ld y;
bool operator== (const Point a) const{
return (a.x == x && a.y == y);
}
};
Point p[120010];
Point st[120010];
Point mini;
int n;
int k;
ld area(Point a, Point b, Point c){
return (ld)1/2 * (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x);
}
bool comp(Point a, Point b){
if(a == mini) return 0;
if(b == mini) return 1;
if(area(mini, a, b) > 0) return 1;
return 0;
}
int main()
{
fin >> n;
mini.x = 1000000010;
mini.y = 1000000010;
for(int i = 0; i < n; i++){
fin >> p[i].x >> p[i].y;
if(p[i].x < mini.x) mini.x = p[i].x, mini.y = p[i].y;
else if(p[i].x == mini.x && p[i].y < mini.y) mini.y = p[i].y;
}
sort(p, p + n, comp);
st[++k] = mini;
st[++k] = p[0];
for(int i = 1; i < n; i++){
if(area(st[k - 1], st[k], p[i]) > 0) st[++k] = p[i];
else{
while(area(st[k - 1], st[k], p[i]) < 0 && k > 1) k--;
st[++k] = p[i];
}
}
fout << k - 1 << '\n';
for(int i = 1; i <= k - 1; i++){
fout << setprecision(12) << fixed << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}