Pagini recente » Cod sursa (job #2279332) | Cod sursa (job #1214895) | Cod sursa (job #2190531) | Autentificare | Cod sursa (job #2556992)
#include<bits/stdc++.h>
#define NMAX 120010
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
int inceput;
struct punct{
double x, y;
}puncte[NMAX], s[NMAX];
void citire()
{
f>>n;
for(int i=1; i<=n; i++)
f>>puncte[i].x>>puncte[i].y;
}
double orientare(punct a, punct b, punct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(punct a, punct b)
{
return (orientare(puncte[1], a, b)<0);
}
void sortare()
{
for(int i=2; i<n; i++)
for(int j=i+1; j<=n; j++)
if(cmp(puncte[i], puncte[j]))
swap(puncte[i], puncte[j]);
}
void prim()
{
int poz=1;
for(int i=1; i<=n; i++)
if(puncte[i].x<puncte[poz].x)
poz=i;
else if(puncte[i].x==puncte[poz].x)
if(puncte[i].y<puncte[poz].y)
poz=i;
swap(puncte[1], puncte[poz]);
}
void prelucrare()
{
s[1]=puncte[1];
s[2]=puncte[2];
inceput=2;
for(int i=3; i<=n; i++)
{
while(inceput>=2 && orientare(s[inceput-1], s[inceput], puncte[i])<0)
inceput--;
s[++inceput]=puncte[i];
}
}
void afisare()
{
g<<fixed;
g<<inceput<<'\n';
for(int i=1; i<=inceput; i++)
g<<setprecision(9)<<s[i].x<<' '<<s[i].y<<'\n';
}
int main()
{
citire();
prim();
sortare();/**
for(int i=1; i<=n; i++)
g<<puncte[i].x<<' '<<puncte[i].y<<'\n';
g<<'\n';*/
prelucrare();
afisare();
return 0;
}