Pagini recente » Cod sursa (job #998910) | Cod sursa (job #1664916) | Cod sursa (job #246055) | Cod sursa (job #195642) | Cod sursa (job #3213176)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 120000;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
long double x,y;
long double angle;
};
int n;
punct points[NMAX + 1];
int H[NMAX + 1];
int nr;
void read(){
fin >> n;
for(int i = 1;i<=n;++i)
fin >> points[i].x >> points[i].y;
}
bool clockwise(punct a, punct b, punct c){
return ((b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y)) < 0;
}
void graham(){
H[1] = 1;
H[2] = 2;
nr = 2;
for(int i = 2;i<=n;++i){
while(nr >= 2 && !clockwise(points[H[nr - 1]], points[H[nr]], points[i]))
nr--;
H[++nr] = i;
}
}
int main(){
read();
for(int i = 2;i<=n;++i)
if(points[i].y < points[1].y)
swap(points[i],points[1]);
points[1].angle = 0;
for(int i = 2;i<=n;++i)
points[i].angle = atan2(points[i].y - points[1].y, points[i].x - points[1].x);
sort(points + 1, points + n + 1, [](punct p1, punct p2){return p1.angle < p2.angle;});
graham();
fout << nr << '\n';
for(int i = 1;i<=nr;++i){
int poz = H[i];
fout << fixed << setprecision(12) << points[poz].x << ' ';
fout << fixed << setprecision(12) << points[poz].y << ' ';
fout << '\n';
}
return 0;
}