Mai intai trebuie sa te autentifici.
Cod sursa(job #3213174)
Utilizator | Data | 12 martie 2024 16:59:10 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.37 kb |
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 120000;
ifstream fin("infasuratoareconvexa.in");
ofstream fout("infasuratoareconvexa.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;
}