Pagini recente » Cod sursa (job #1893374) | Cod sursa (job #1919969) | Cod sursa (job #603205) | Cod sursa (job #474760) | Cod sursa (job #1529069)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,top,pos,S[120010];
typedef pair <double, double> Tip;
Tip V[120010];
double Det(Tip a, Tip b, Tip c)
{ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
bool cmp(Tip a, Tip b)
{ return (Det(V[1], a, b) < 0);}
int main()
{
f>>n;
pos=1;
for(int i=1;i<=n;i++)
{
f>>V[i].x>>V[i].y;
if(V[i]<V[pos]) pos = i;
}
swap(V[1],V[pos]);
sort(V+2,V+n+1,cmp);
S[++top]=1;
for(int i=2;i<=n;i++)
{
while(top>1 && Det(V[S[top-1]],V[S[top]],V[i])>0)
top--;
S[++top] = i;
}
g<<top<<'\n';
while(top)
{
g<<fixed<<setprecision(6)<<V[S[top]].x<<' '<<V[S[top]].y<<'\n';
top--;
}
g.close();
return 0;
}