Pagini recente » Cod sursa (job #2093786) | Cod sursa (job #2575873) | Cod sursa (job #3200491) | Cod sursa (job #1914165) | Cod sursa (job #2984965)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
double ariemax;
struct punct{
double x , y;
};
double orientation( punct a, punct b, punct c ){
return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
int n;
punct puncte[120001];
bool cmp(punct a , punct b){
return orientation(puncte[1],a,b)<0;
}
void infasuratoare(){
int minp = 1;
for(int i = 2 ; i <= n ; i++){
if( puncte[minp].y > puncte[i].y || (puncte[minp].y == puncte[i].y && puncte[minp].x < puncte[i].x)){
minp = i;
}
}
swap(puncte[minp],puncte[1]);
sort(puncte + 2 , puncte + n + 1 ,cmp);
vector <punct> hull;
hull.push_back(puncte[1]);
hull.push_back(puncte[2]);
for(int i = 3 ; i <= n ; i++){
while( hull.size() >= 2 && orientation(hull[hull.size()-2] , hull.back() ,puncte[i])>=0) hull.pop_back();
hull.push_back(puncte[i]);
}
double arie;
cout << hull.size() << '\n';
for(auto it : hull){
cout << fixed << setprecision(13) << it.x << ' ' << it.y;
cout << '\n';
}
}
int main(){
cin >> n;
for(int i = 1 ; i <= n ;i++){
cin >> puncte[i].x >> puncte[i].y;
}
infasuratoare();
return 0;
}