Pagini recente » Cod sursa (job #299995) | Cod sursa (job #2685221) | Cod sursa (job #2877470) | Cod sursa (job #51867) | Cod sursa (job #1806719)
#include <bits/stdc++.h>
using namespace std;
//struct point{
// double x, y;
//};
typedef pair<double, double> point;
point arr[120001];
int n;
double det(point a, point b, point c){
return(a.first * b.second) + (b.first * c.second) + (c.first * a.second) - (b.second * c.first)-
(c.second * a.first) - (a.second * b.first);
}
int criteria(const point& a, const point& b){
if(det(arr[0], a, b) < 0)
return(1);
return(0);
}
void Sort0(){
int k = 0;
for(int i = 1; i < n; i++)
if(arr[i] < arr[k])
k = i;
swap(arr[0], arr[k]);
sort(arr + 1, arr + n, criteria);
}
int main(){
ifstream cin("infasuratoare.in");
//ifstream cin("input.in");
ofstream cout("infasuratoare.out");
cin >> n;
for(int i = 0; i < n; i++)
cin >> arr[i].first >> arr[i].second;
Sort0();
point st[120001];
st[0] = arr[0];
st[1] = arr[1];
int elem = 1;
for(int i = 2; i<= n; i++){
while(det(st[elem - 1] , st[elem] , arr[i]) > 0 && elem > 0)
elem--;
st[elem + 1] = arr[i];
elem++;
}
cout << elem << endl;
for(int i = elem - 1; i > -1; i--)
cout << fixed << setprecision(10) << st[i].first << ' ' << st[i].second << endl;
}