Pagini recente » Cod sursa (job #498329) | Cod sursa (job #1141018) | Cod sursa (job #2913237) | Cod sursa (job #2087195) | Cod sursa (job #967814)
Cod sursa(job #967814)
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream ff("test.in");
//ofstream gg("test.out");
#define gg cout
#define max 120001
#define eps 1e-8
struct pct{ double x,y; pct(double x0=0,double y0=0){x=x0;y=y0;}
void af(){ cout << "(" << x << "," << y << ") "; }} ss[max], su[max], sd[max];
int n, n1, n2;
bool cmp(pct a, pct b){ return a.x<b.x; }
double dlt(pct a, pct b, pct c){
return a.x*b.y+b.x*c.y+c.x*a.y-b.x*a.y-c.x*b.y-a.x*c.y;
}
void sub(){
su[n1++]=sd[n2++]=ss[0];
for(int i=1;i<n-1;i++)
if(dlt(ss[0],ss[n-1],ss[i])>eps) su[n1++]=ss[i]; else
if(dlt(ss[0],ss[n-1],ss[i])<eps) sd[n2++]=ss[i];
su[n1++]=sd[n2++]=ss[n-1];
}
void sup(){
int n=2;
for(int i=2;i<n1;i++){
while(n>=2 && dlt(su[n-2],su[i],su[n-1]) < eps)n--;
su[n++]=su[i];
}
n1=n;
}
void sdo(){
int n=2;
for(int i=2;i<n2;i++){
while(n>=2 && dlt(sd[n-2],sd[i],sd[n-1]) > eps)n--;
sd[n++]=sd[i];
}
n2=n;
}
int main(){
ff >> n;
for(int i=0;i<n;i++) ff >> ss[i].x >> ss[i].y;
sort(ss, ss+n, cmp);
sub();
sup();
sdo();
cout << n1+n2-2 << "\n";
for(int i=n1-1;i>=0;i--) cout << su[i].x << " " << su[i].y << "\n";
for(int i=1;i<n2-1;i++) cout << sd[i].x << " " << sd[i].y << "\n";
return 0;
}