Cod sursa(job #2058567)

Utilizator Consti.001FMI Dranca Constantin Consti.001 Data 5 noiembrie 2017 20:16:25
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#define Nmax 120010
#define INF 1<<30
#include<iostream>

using namespace std;
ifstream f("data.in");
ofstream g("data.out");
struct punct
{
    double x,y,panta;
};
int cmp ( punct a, punct b)
{
    if(a.panta==b.panta)
    {
        if(a.x==b.x) return a.y<b.y;
        return a.x<b.x;
    }

    return a.panta<b.panta;
}

int convex(punct v[],int s[],int i, int k)
{
    punct a,b,c;
    double S;
    a=v[s[k-1]];
    b=v[s[k]];
    c=v[i];
    S =(a.x-c.x)*(b.y-a.y)+(a.x-b.x)*(a.y-c.y);
    if(S>0) return 1;
    return 0;
}


int main()
{
    int poz=0,k=0,s[6];
    punct v[5],o,aux,scos;
    o.x=o.y=INF;

    for(int i=1;i<=4;++i)
    {
        f>>v[i].x>>v[i].y;
        if((v[i].x<o.x)||((v[i].x==o.x)&&(v[i].y<o.y)))
            o=v[i],poz=i;
    }
    aux=v[1];
    v[1]=v[poz];
    v[poz]=aux;


    for(int i=2;i<=4;i++)
        v[i].panta=(v[i].y-o.y)/(v[i].x-o.x);

    sort(v+2,v+5,cmp);
    s[1]=1; s[2]=2; k=2;

        for(int i=3;i<=4;i++)
    {
        while (!convex(v,s,i,k)&&k>2)
         { scos=v[s[k]];k--;}
        s[++k]=i;
    }
    /*for(int i=1 ;i<=k;++i)
    cout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";*/
    if(k==3)
    {
        if((v[2].panta==v[3].panta)&&(v[3].panta==v[4].panta)&&(v[4].panta==v[4].panta))  //Toate patru sunt coliniare
        {
            g<<"Multimea 1:\n"<<fixed<<setprecision(6)<<v[1].x<<" "<<fixed<<setprecision(6)<<v[1].y<<"\n";
            g<<fixed<<setprecision(6)<<v[3].x<<" "<<fixed<<setprecision(6)<<v[3].y<<"\n\n\n";

            g<<"Multimea 2:\n";
            g<<fixed<<setprecision(6)<<v[2].x<<" "<<fixed<<setprecision(6)<<v[2].y<<"\n";
            g<<fixed<<setprecision(6)<<v[4].x<<" "<<fixed<<setprecision(6)<<v[4].y;
        }
        else        //Avem un triunghi
        {

            g<<"Multimea 1:\n";
            for(int i=1;i<=k;++i)
            g<<fixed<<setprecision(6)<<v[s[i]].x<<" "<<fixed<<setprecision(6)<<v[s[i]].y<<"\n";
            g<<"Multimea 2:\n";
            g<<fixed<<setprecision(6)<<scos.x<<" "<<fixed<<setprecision(6)<<scos.y;
        }

    }
    else
    if(v[s[2]].panta==v[s[3]].panta)//Al doilea punct din infasuratoare e pe o latura a triunghiului
    {
        g<<"Multimea 1:\n";
        g<<fixed<<setprecision(6)<<v[s[1]].x<<" "<<fixed<<setprecision(6)<<v[s[1]].y<<"\n";
        g<<fixed<<setprecision(6)<<v[s[3]].x<<" "<<fixed<<setprecision(6)<<v[s[3]].y<<"\n";
        g<<fixed<<setprecision(6)<<v[s[4]].x<<" "<<fixed<<setprecision(6)<<v[s[4]].y<<"\n";
        g<<"Multimea 2:\n";
        g<<fixed<<setprecision(6)<<v[s[2]].x<<" "<<fixed<<setprecision(6)<<v[s[2]].y<<"\n";
    }
    else    //Avem patrulater
    {

        g<<"Multimea 1:\n";
        g<<fixed<<setprecision(6)<<v[s[1]].x<<" "<<fixed<<setprecision(6)<<v[s[1]].y<<"\n";
        g<<fixed<<setprecision(6)<<v[s[3]].x<<" "<<fixed<<setprecision(6)<<v[s[3]].y<<"\n";
        g<<"Multimea 2:\n";
        g<<fixed<<setprecision(6)<<v[s[2]].x<<" "<<fixed<<setprecision(6)<<v[s[2]].y<<"\n";
        g<<fixed<<setprecision(6)<<v[s[4]].x<<" "<<fixed<<setprecision(6)<<v[s[4]].y<<"\n";

    }

    return 0;
}