Pagini recente » Cod sursa (job #87177) | Cei mai harnici utilizatori infoarena | Cod sursa (job #318803) | Cod sursa (job #1146697) | Cod sursa (job #529241)
Cod sursa(job #529241)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NMAX 120012
#define INF 1<<30
using namespace std;
struct puncte{
double x,y;
}a[NMAX];
int n,k,st[NMAX],ind[NMAX],pi;
double xo,yo;
struct cmp
{
bool operator () (const int &i,const int &j)
{
return (long double)(a[i].x - xo) * (a[j].y - yo) > (long double)(a[j].x - xo) * (a[i].y - yo);
}
};
long double convex(int i,int j, int k)
{
long double d;
d=(long double) (a[i].x*a[j].y+a[j].x*a[k].y+a[k].x*a[i].y-a[i].x*a[k].y-a[j].x*a[i].y-a[k].x*a[j].y);
return d;
}
void citire()
{
int i;
ifstream f("infasuratoare.in");
f>>n;
xo=yo=INF;
for(i=1;i<=n;i++)
{
f>>a[i].x>>a[i].y;
if(a[i].y<yo || a[i].y==yo&&a[i].x<xo)
{
xo=a[i].x;
yo=a[i].y;
pi=i;
}
}
f.close();
}
void scrie()
{
int i;
ofstream g("infasuratoare.out");
g<<k<<"\n";
for(i=1;i<=k;i++)
g<<fixed<<setprecision(6)<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
g.close();
}
void rezolva()
{
int i;
for(i=1;i<=n;i++)
{
if(i==pi) continue;
ind[++ind[0]]=i;
}
sort(ind+1,ind+ind[0]+1,cmp());
st[++k]=pi;
for(i=1;i<=ind[0];i++)
{
if(ind[i]==pi) continue;
while(convex(st[k],st[k-1],ind[i])>0 && k>=2) k--;
st[++k]=ind[i];
}
}
int main()
{
citire();
rezolva();
scrie();
return 0;
}