Pagini recente » Cod sursa (job #1108371) | Cod sursa (job #2962302) | Cod sursa (job #2562257) | Cod sursa (job #2102148) | Cod sursa (job #967891)
Cod sursa(job #967891)
#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 <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("infasuratoare.in");
ofstream gg("infasuratoare.out");
#define max 120001
#define eps 1e-12
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]) > 0) su[n1++]=ss[i]; else
if(dlt(ss[0],ss[n-1],ss[i]) < 0) 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--; // dlt<=0 (0==eps)
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--; // dlt>=0 (0==-eps)
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();
gg << n1+n2-2 << "\n";
gg << setprecision(6) << fixed;
for(int i=n1-1;i>=0;i--) gg << su[i].x << " " << su[i].y << "\n";
for(int i=1;i<n2-1;i++) gg << sd[i].x << " " << sd[i].y << "\n";
return 0;
}