Cod sursa(job #528353)

Utilizator giuliastefGiulia Stef giuliastef Data 2 februarie 2011 17:46:31
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <algorithm>
#include <iomanip.h>
#define NMAX 120012
using namespace std;
struct puncte{
       double x,y;
       } a[NMAX];
       
int i,st[NMAX],n,k;
double x,y,xo,yo;
       
bool cmp(puncte x,puncte y)
{
     return (double)(x.x - a[0].x) * (y.y - a[0].y) > (double)(y.x - a[0].x) * (x.y - a[0].y);    
}

inline int e_convex(double x1, float y1, float x2, float y2, float x3, float y3)
{
    long double d;
    d=(long double)x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
    if(d>=0) return 1;
    return 0;
}

int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    f>>xo>>yo;
    for(i=2;i<=n;i++)
    {
     f>>x>>y;
     if(y<yo) a[++k].x=xo, a[k].y=yo, xo=x, yo=y;
     else
      if(y==yo&&x<xo)  a[++k].x=xo, a[k].y=yo, xo=x, yo=y;
      else
       a[++k].x=x, a[k].y=y;
    }
    a[0].x=xo;
    a[0].y=yo;
    sort(a+1,a+k+1,cmp);
    st[st[0]=1]=0;
    for(i=1;i<=k;i++)
    {
     while((!e_convex(a[st[st[0]-1]].x, a[st[st[0]-1]].y, a[st[st[0]]].x, a[st[st[0]]].y,a[i].x,a[i].y))&&st[0]>=2) st[0]--;
     st[++st[0]]=i;
    }  
    g<<st[0]<<"\n";
    g.setf(ios::fixed);
    g.setf(ios::showpoint);
    g.precision(6);
    for(i=1;i<=st[0];i++)
     g<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
    f.close();
    g.close();
    return 0;
}