Pagini recente » Cod sursa (job #3229332) | Cod sursa (job #611787) | Cod sursa (job #1825453) | Cod sursa (job #2630349) | Cod sursa (job #2158460)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
using namespace std;
struct pct{
double x, y, p;
} v[120001];
bool sortare (pct a, pct b){
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
int arie (int i, int j, int l)
{
int a = v[i].x * v[j].y - v[j].y * v[l].x + v[j].x * v[l].y
- v[l].y * v[i].x + v[l].x * v[i].y - v[i].y * v[j].x;
if (a < 0)
return -1;
if (a > 0)
return 1;
return 0;
}
int n, w[120001];
int main ()
{
ifstream in("infasuratoare.in");
freopen("infasuratoare.out","w",stdout);
int l;
in >> n;
for (int i=1; i<=n; i++){
in >> v[i].x >> v[i].y;
}
sort (v+1, v+n+1, sortare);
w[1] = 1;
l = 1;
for (int i=2; i<n; i++){
v[i].p = arie (1, n, i);
if (v[i].p < 0){
if (l == 1){
l++;
w[l] = i;
}
else{
while(arie (w[l], w[l-1], i) >= 0 ){
l --;
}
l ++;
w[l] = i;
}
}
}
if (arie (n, w[l-1], w[l]) < 0){
l --;
}
l++;
w[l] = n;
for (int i=n-1; i>1; i--){
if (v[i].p > 0){
if (w[l] == n){
l ++;
w[l] = i;
}
else{
while(arie (w[l], w[l-1], i) >= 0 ){
l --;
}
l ++;
w[l] = i;
}
}
}
if (arie (1, w[l-1], w[l]) < 0){
l --;
}
printf("%d\n",l);
for (int i=1; i<=l; i++){
printf("%.6f %.6f\n",v[w[i]].x,v[w[i]].y);
}
return 0;
}