Cod sursa(job #1195357)

Utilizator niktudyNica Tudor niktudy Data 6 iunie 2014 22:31:10
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.75 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define nmax 120000
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct
{
    double x,y;
} a[nmax],aux,s[nmax],b[nmax];
int n,m,p0,varf;
void citire ()
{
    int i;
    fin>>n;
    p0=1;
    for (i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
        if (a[i].y<a[p0].y||(a[i].y==a[p0].y&&a[i].x<a[p0].x))
            p0=i;
    }
    for (i=1;i<=m;i++)
        fin>>b[i].x>>b[i].y;
    b[m+1]=b[1];
    fin.close ();
}
void afisare ()
{
    int i;
    fout<<varf<<'\n';
    for (i=1;i<=varf;i++)
        //fout<<"add_to_list("<<s[i].x<<','<<s[i].y<<");"<<'\n';
        fout<<s[i].x<<' '<<s[i].y<<'\n';
    fout.close ();
}
int crt (punct p1,punct p2)
{
    p1.x-=a[p0].x;
    p2.x-=a[p0].x;
    p1.y-=a[p0].y;
    p2.y-=a[p0].y;
    double u1,u2,PI=3.14159265;
    u1=atan(p1.y/p1.x)*180/PI;
    u2=atan(p2.y/p2.x)*180/PI;
    if (u1<0)
        u1+=180;
    if (u2<0)
        u2+=180;
    //fout<<p1.x<<' '<<p1.y<<' '<<p2.x<<' '<<p2.y<<' '<<u1<<' '<<u2<<'\n';
    if (u1-u2<=0.0001&&u1-u2>=-0.0001)
    {
        double d1,d2;
        d1=sqrt(p1.x*p1.x+p1.y*p1.y);
        d2=sqrt(p2.x*p2.x+p2.y*p2.y);
        return d1<d2;
    }
    return (u1<u2);
}
int produs (punct p1,punct p2,punct p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
void infas_convexa ()
{
    int o,i;
    aux=a[p0];
    a[p0]=a[1];
    a[1]=aux;
    p0=1;
    sort (a+2,a+n+1,crt);
    varf=2;
    s[1]=a[1];
    s[2]=a[2];
    for (i=3;i<=n;i++)
    {
        o=produs (s[varf-1],s[varf],a[i]);
        while (o<=0&&varf>1)
        {
            varf--;
            if (!o)
                break;
            o=produs (s[varf-1],s[varf],a[i]);
        }
        s[++varf]=a[i];
    }
    s[varf+1]=s[1];
}
void ecdr (double &aa,double &bb,double &cc,punct p1,punct p2)
{
    aa=p1.y-p2.y;
    bb=p2.x-p1.x;
    cc=p1.x*p2.y-p2.x*p1.y;
}
int verif (punct s1,punct s2,punct b)
{
    if (s1.x>s2.x)
    {
        aux=s2;
        s2=s1;
        s1=aux;
    }
    if (s1.x<b.x&&b.x<s2.x)
        return 1;
    if (s1.y>s2.y)
    {
        aux=s2;
        s2=s1;
        s1=aux;
    }
    if (s1.y<b.y&&b.y<s2.y)
        return 1;
    return 0;
}
void testare_pext ()
{
    int i,j,o1,o2,ok;
    double aa,bb,cc;
    for (i=1;i<=varf;i++)
    {
        ok=0;
        ecdr (aa,bb,cc,s[i],s[i+1]);
        //fout<<aa<<' '<<bb<<' '<<cc<<'\n';
        for (j=1;j<=m&&!ok;j++)
            if (verif (s[i],s[i+1],b[j])==1)
            {
                fout<<b[j].x<<' '<<b[j].y<<' '<<b[j+1].x<<' '<<b[j+1].y<<' ';
                o1=aa*b[j].x+bb*b[j].y+cc;
                while (!o1&&j<=m)
                {
                    j++;
                    o1=aa*b[j].x+bb*b[j].y+cc;
                }
                for (j++;j<=m;j++)
                {
                    if (!verif(s[i],s[i+1],b[j]))
                        break;
                    o2=aa*b[j].x+bb*b[j].y+cc;
                    while (!o2)
                    {
                        j++;
                        o2=aa*b[j].x+bb*b[j].y+cc;
                    }
                    if ((o1<0&&o2>0)||(o1>0&&o2<0))
                    {
                        //calc_traseu ();
                        fout<<b[j].x<<' '<<b[j].y<<' '<<b[j+1].x<<' '<<b[j+1].y<<' ';
                        fout<<s[i].x<<' '<<s[i].y<<' '<<s[i+1].x<<' '<<s[i+1].y<<'\n';
                        ok=1;
                        break;
                    }
                    o1=o2;
                }
            }
    }
}
int main()
{
    citire ();
    infas_convexa ();
    //testare_pext ();
    afisare ();
    return 0;
}