Pagini recente » Cod sursa (job #2725294) | Cod sursa (job #1047122) | Cod sursa (job #2976301) | Cod sursa (job #2343004) | Cod sursa (job #2142435)
#include <bits/stdc++.h>
using namespace std;
const int N = 120'005;
pair <double, double> v[N];
pair <double, double> ax[N];
pair <double, double> st[N];
int signDet(pair<double, double> A, pair<double, double> B, pair<double, double> C){
double det = A.first * B.second + B.first * C.second + C.first * A.second - A.first * C.second - C.first * B.second - B.first * A.second;
if(det == 0){
return 0;
}
return (det < 0 ? 1 : -1);
}
bool comp(pair<double, double> A, pair<double, double> B){
int sg = signDet(v[1], A, B);
if(sg == 0){
return A.first < B.first;
}
return sg < 0;
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
scanf("%d", &n);
int id = 0;
for(int i = 1;i <= n;i++){
scanf("%lf %lf", &v[i].first, &v[i].second);
if(i == 1){
id = i;
}else if(v[i].second < v[id].second){
id = i;
}else if(v[i].second == v[id].second && v[i].first < v[id].first){
id = i;
}
}
swap(v[1], v[id]);
sort(v + 2, v + n + 1, comp);
int nn = 0;
for(int i = 2;i < n;i++){
if(signDet(v[1], v[i], v[i + 1]) == 0){
continue;
}
ax[++nn] = v[i];
}
ax[++nn] = v[n];
st[1] = v[1];
st[2] = ax[1];
int e = 2;
for(int i = 2;i <= nn;i++){
while(e > 1 && signDet(st[e - 1], st[e], ax[i]) > 0){
e--;
}
st[++e] = ax[i];
}
printf("%d\n", e);
for(int i = 1;i <= e;i++){
printf("%.8f %.8f\n", st[i].first, st[i].second);
}
return 0;
}