Pagini recente » Cod sursa (job #2986671) | Cod sursa (job #3236757) | Cod sursa (job #3293151) | Cod sursa (job #3258825) | Cod sursa (job #847076)
Cod sursa(job #847076)
#include <algorithm>
#include <vector>
#include <stack>
#include <stdio.h>
using namespace std;
#define N_MAX 120002
#define ld long double
#define x first
#define y second
typedef pair <double, double> p;
p a[N_MAX];
int n;
int pivot = 0;
vector <int> st;
struct cmp{
bool operator () (const p &aa, const p &bb) const{
return (ld) (bb.x - a[pivot].x) * (aa.y - a[pivot].y) < (ld) (bb.y - a[pivot].y) * (aa.x - a[pivot].x);
}
};
ld sign(const int &i, const int &j, const int &k){
return (ld) (a[k].x - a[i].x) * (a[j].y - a[i].y) - (ld) (a[k].y - a[i].y) * (a[j].x - a[i].x);
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(int i = 0; i < n; i ++){
scanf("%lf %lf", &a[i].x, &a[i].y);
}
for(int i = 0; i < n; i ++){
if(a[i].x < a[pivot].x || a[i].x == a[pivot].x && a[i].y < a[pivot].y){
pivot = i;
}
}
swap(a[pivot], a[0]);
pivot = 0;
sort(a + 1, a + n, cmp());
st.push_back(pivot);
for(int i = 1; i < n; i ++){
while(st.size() > 1 && sign(st[st.size() - 2], st[st.size() - 1], i) > 0){
st.pop_back();
}
st.push_back(i);
}
printf("%d\n", st.size());
for(int i = 0; i < (int) st.size(); i ++){
printf("%lf %lf\n", a[ st[i] ].x, a[ st[i] ].y);
}
return 0;
}