Cod sursa(job #755531)

Utilizator StefanCenusaStefan Cenusa StefanCenusa Data 6 iunie 2012 09:34:02
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include<algorithm>
#include<math.h>
using namespace std;
#define maxn 120000
#define INF 1000000000

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

double X[maxn],Y[maxn];
long double V[maxn];
int pi,IND[maxn],n,ST[maxn];

long double semn(int i1,int i2,int i3);
bool cmpf(int i,int j);

int main()
{
    int i;
    X[0]=INF;Y[0]=INF;
    fin>>n;
    pi=0;
    for(i=1;i<=n;i++)
        {
            fin>>X[i]>>Y[i];
            if(X[i]<X[pi] || (X[i]==X[pi] && Y[i]<Y[pi])) pi=i;
        }
    for(i=1;i<=n;i++)
        {
            if(i==pi) continue; 
            IND[++IND[0]]=i;
        }
    sort(IND+1,IND+IND[0]+1,cmpf);
    ST[ST[0]=1]=pi;
	for(i=1;i<=IND[0];i++)
        {
            if(IND[i]==pi) continue;
            while(ST[0]>=2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i])>0) --ST[0];
            ST[++ST[0]] = IND[i];
        }
	ST[++ST[0]]=pi;
	fout<<ST[0]-1<<'\n';
	reverse(ST+1,ST+ST[0]+1);
	for(int i = 1;i < ST[0]; ++i)
        {
            fout<<X[ST[i]]<<' '<<Y[ST[i]]<<'\n';
        }
	return 0;
}

bool cmpf(int i,int j)
{
	return (double)(X[i] - X[pi]) * (Y[j] - Y[pi]) < (double)(X[j] - X[pi]) * (Y[i] - Y[pi]);
}

long double semn(int i1,int i2,int i3)
{
	return (long double)X[i1]*Y[i2]+X[i2]*Y[i3]+X[i3]*Y[i1]-Y[i1]*X[i2]-Y[i2]*X[i3]-Y[i3]*X[i1];
}