Pagini recente » Cod sursa (job #2132230) | Cod sursa (job #330413) | Cod sursa (job #633016) | Cod sursa (job #946737) | Cod sursa (job #3215420)
#include <bits/stdc++.h>
using namespace std;
struct punct{
double x, y;
};
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120001;
int n, ind = 1;
double minY = INT_MAX;
vector<punct> puncte;
punct hull[NMAX];
inline bool isCounterClockwise(double x1, double y1, double x2, double y2, double x3, double y3){
return (long double)(y3 - y2) * (x2 - x1) - (x3 - x2) * (y2 - y1) > 0;
}
int main(){
fin >> n;
for(int i = 0; i < n; i++){
double x, y;
fin >> x >> y;
if(y < minY){
minY = y;
hull[0] = {x, y};
}
puncte.push_back({x, y});
}
sort(puncte.begin(), puncte.end(), [](punct a, punct b){
return atan2(a.y - hull[0].y, a.x - hull[0].x) < atan2(b.y - hull[0].y, b.x - hull[0].x);
});
hull[ind++] = puncte[1];
for(int i = 2; i < puncte.size(); i++){
double x = puncte[i].x, y = puncte[i].y;
while(!isCounterClockwise(hull[ind - 2].x, hull[ind - 2].y, hull[ind - 1].x, hull[ind - 1].y, x, y) && ind >= 2) ind--;
hull[ind++] = {x, y};
}
fout << ind << '\n';
fout << fixed;
for(int i = 0; i < ind; i++) fout << setprecision(6) << hull[i].x << ' ' << hull[i].y << '\n';
return 0;
}