Pagini recente » Cod sursa (job #2737129) | Cod sursa (job #181900) | Cod sursa (job #1272529) | Cod sursa (job #255329) | Cod sursa (job #967879)
Cod sursa(job #967879)
#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]) + eps > 0) su[n1++]=ss[i]; else
if(dlt(ss[0],ss[n-1],ss[i]) - eps < 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 < 0)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 > 0)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;
//for(int i=0;i<n;i++) gg << ss[i].x << "\t" << ss[i].y << "\n";
sort(ss, ss+n, cmp);
sub();
//for(int i=0;i<n1;i++) gg << su[i].x << " " << su[i].y << "\n";
sup();
sdo();
gg << n1+n2-2 << "\n";
for(int i=n1-1;i>=0;i--) gg << setprecision(13) << su[i].x << " " << (double)su[i].y << "\n";
for(int i=1;i<n2-1;i++) gg << setprecision(13) << sd[i].x << " " << (double)sd[i].y << "\n";
return 0;
}