Pagini recente » Cod sursa (job #2970516) | Cod sursa (job #2600841) | Cod sursa (job #136061) | Cod sursa (job #2178609) | Cod sursa (job #743606)
Cod sursa(job #743606)
#include<fstream>
#include<algorithm>
#define Nmax 120002
#define INF 1<<30
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int ST[Nmax], nxt[Nmax];
struct punct {float x, y;};
punct a[Nmax];
int N, P, i;
inline bool cmp(int i, int j)
{return (a[i].x - a[P].x) * (a[j].y - a[P].y) < (a[j].x - a[P].x) * (a[i].y - a[P].y);}
inline double semn(int i1, int i2, int i3)
{ return a[i1].x * a[i2].y + a[i3].x * a[i1].y + a[i2].x * a[i3].y - a[i3].x * a[i2].y - a[i2].x * a[i1].y - a[i1].x * a[i3].y;}
void rezolva()
{
a[P].x = a[P].y = INF;
for(int i=1; i<=N; ++i)
if(a[i].x < a[P].x || (a[i].x == a[P].x && a[i].y < a[P].y))
P = i;
for(int i =1; i<=N; ++i)
if(i != P)
nxt[++nxt[0]] = i;
sort(nxt+1, nxt + nxt[0] + 1, cmp);
ST[++ST[0]] = P;
for(int i=1; i<=nxt[0]; ++i)
{
if(nxt[i] == P)
continue;
while(ST[0] >= 2 && semn(ST[ST[0]-1], ST[ST[0]], nxt[i]) > 0)
ST[0]--;
ST[++ST[0]] = nxt[i];
}
}
void afisare()
{
fout<<ST[0]<<'\n';
reverse(ST+1, ST + ST[0] + 1);
for(i=1;i<=ST[0];++i)
fout<<a[ST[i]].x<<' '<<a[ST[i]].y<<'\n';
}
int main()
{
fin>>N;
for(i=1;i<=N;++i)
fin>>a[i].x>>a[i].y;
rezolva();
afisare();
fin.close();
fout.close();
return 0;
}