Pagini recente » Cod sursa (job #2332258) | Cod sursa (job #1213536) | Cod sursa (job #752004) | Cod sursa (job #642824) | Cod sursa (job #1117854)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <queue>
#include <string>
#include <map>
#include <set>
#define DN 120005
#define pb push_back
#define mp make_pair
#define per pair<double,double>
#define INF (1<<30)
#define LL long long
#define un unsigned
#define x first
#define y second
using namespace std;
per p[DN],st[DN];
int sz;
/*
bool cmp(per a,per b){
return atan2(a.y-p[1].y,a.x-p[1].x) < atan2(b.y-p[1].y,b.x-p[1].x);
}*/
double ccw( per a, per b, per c){
return ( b.x - a.x ) * ( c.y - a.y ) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(per a,per b){
return ccw(p[1],a,b) < 0;
}
int main()
{
int n;
ifstream f("infasuratoare.in");
f>>n;
f>>p[1].x>>p[1].y;
for(int i=2;i<=n;++i){
f>>p[i].x>>p[i].y;
if(p[1].x == p[i].x && p[1].y > p[i].y)
swap(p[i],p[1]);
if(p[1].x > p[i].x)
swap(p[1],p[i]);
}
sort(p+2,p+n+1,cmp);
st[ ++sz ] = (p[1]);
st[ ++sz ] = (p[2]);
for(int i=3;i<=n;++i){
for( ; sz>=2 && ccw(st[ sz -1 ],st[sz],p[i]) > 0 ; )
--sz;
st[++sz] = p[i];
}
cout<<sz<<"\n";
for(int i=1;i<=sz;++i)
cout<<fixed<< setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}