Pagini recente » Cod sursa (job #2253273) | Cod sursa (job #3169523) | Cod sursa (job #689270) | Cod sursa (job #675275) | Cod sursa (job #529173)
Cod sursa(job #529173)
#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];
double xo,yo;
bool cmp(puncte x, puncte y)
{
return (long double)(x.x - a[0].x) * (y.y - a[0].y) > (long double)(y.x - a[0].x) * (x.y - a[0].y);
}
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;
}
}
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;
a[0].x=xo;
a[0].y=yo;
sort(a+1,a+n+1,cmp);
st[++k]=0;
for(i=1;i<=n;i++)
{
if(a[i].x==xo && a[i].y==yo) continue;
while(convex(st[k],st[k-1],i)>0 && k>=2) k--;
st[++k]=i;
}
}
int main()
{
citire();
rezolva();
scrie();
return 0;
}