Pagini recente » Cod sursa (job #760081) | Istoria paginii runda/simulare-cartita-46 | Cod sursa (job #979072) | Cod sursa (job #2122584) | Cod sursa (job #1219155)
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
#define EPS 0.00001
using namespace std;
int N;
vector<pair<double,double> >P,hull;
pair<double,double> stak[120005];
int vf;
void push(pair<double,double> P){
stak[++vf] = P;
}
void pop(){
stak[vf] = make_pair(0,0);
--vf;
}
double abso(double nr){
if(nr < 0)
return -nr;
return nr;
}
double semn(pair<double,double> p1, pair<double,double> p2, pair<double,double> p3){
double rez = (p1.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p1.y-p3.y);
if(abso(rez - 0.0000001) < EPS)
return 0;
return rez;
}
void read( void )
{
pair<double,double> pct;
scanf("%d",&N);
for(int i = 1; i <= N; ++i){
scanf("%lf%lf",&pct.x,&pct.y);
P.push_back(pct);
}
}
void solve( void )
{
sort(P.begin(),P.end());
pair<double,double> Pmin = P[0],Pmax = P[P.size()-1];
push(Pmin); /// sigur apartine
for(int i = 1; i < N; ++i)
if(semn(Pmin,Pmax,P[i]) >= 0 || i == N)
{
while(vf >= 2 && semn(stak[vf-1],stak[vf],P[i]) >= 0) /// fara egal si le ia si pe alea coliniare
pop();
push(P[i]);
}
for(int i = N - 2; i >= 0; --i)
if(semn(Pmax,Pmin,P[i]) >=0 || i == 0)
{
while(vf >= 2 && semn(stak[vf-1],stak[vf],P[i]) >= 0) /// fara egal si le ia si pe alea coliniare
pop();
push(P[i]);
}
}
void print(void)
{
printf("%d\n",vf - 1);
while(vf > 1)
{
printf("%lf %lf\n",stak[vf].x,stak[vf].y);
--vf;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
solve();
print();
return 0;
}