Pagini recente » Cod sursa (job #3039238) | Cod sursa (job #357037) | Cod sursa (job #2141151) | Cod sursa (job #2216409) | Cod sursa (job #1021731)
#include <fstream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#define mx 120009
#define PLUS 1000000000
#define e 0.000000000001
#define float long double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, LowestPoint,H;
pair<float,float> point[mx],stack[mx];
void Read();//
void SortPoints();
void Solve();
void Write();
int main()
{
Read();
SortPoints();
Solve();
Write();
return 0;
}
inline float trig(pair<float,float>& A,const pair<float,float>& B, const pair<float,float>& C)
{
return (B.first-A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first);
}
inline int comp(const pair<float,float>& A, const pair<float,float>& B)
{
return trig(point[0],A,B)<e;
}
void Solve()
{
stack[0]=point[0];
stack[1]=point[1];
H=2;
for(int i=2;i<n;i++)
{
while(H>1 && trig(stack[H-1],stack[H],point[i])>e)
--H;
stack[++H]=point[i];
}
}
void SortPoints()
{
swap(point[0],point[LowestPoint]);
sort(point+1,point+n,comp);
}
void Write()
{
g<<H+1<<'\n';
for(int i=H;i>=0;--i)
g<<setprecision(12)<<stack[i].first<<'\t'<<stack[i].second<<'\n';
}
void Read()
{
f>>n;
for(int i=0;i<n;++i)
{
f>>point[i].first>>point[i].second;
/* if(point[i].first<=point[LowestPoint].first)
{
if(point[i].first==point[LowestPoint].first)
LowestPoint=(point[i].second<point[LowestPoint].second)? i:LowestPoint;
else
LowestPoint=i;
}*/
if(point[i]<point[LowestPoint])
LowestPoint=i;
}
}