Cod sursa(job #1301547)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 26 decembrie 2014 02:41:47
Problema Hashuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#define mod 1000
using namespace std;
ifstream f("plagiat.in");
ofstream g("plagiat.out");
struct punct{int x,y;}p[403];
long long t,n,i,j,T,k,gasit,l,nr;
float v[5];
struct triunghi{float b,c,d,e;}aux;
vector <triunghi> Hash[mod+3];
float panta(punct p1,punct p2)
{
    return (float)(p1.y-p2.y)/(float)(p1.x-p2.x);
}
float dist(punct p1,punct p2)
{
    return (float)sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int aria(punct p1,punct p2,punct p3){
    return 4*abs((p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y));
}
bool cmp(triunghi t1,triunghi t2)
{
    return t1.b<t2.b||(t1.b==t2.b && t1.c<t2.c)||(t1.b==t2.b && t1.c==t2.c && t1.d<t2.d)||(t1.b==t2.b && t1.c==t2.c && t1.d==t2.d && t1.e<t2.e);
}
int main()
{
    f>>T;
    while(T--)
    {
        f>>n;gasit=0;k=0;
        for(i=1;i<=n;i++)
            f>>p[i].x>>p[i].y;
        for(i=1;i<n-1 && !gasit;i++)
            for(j=i+1;j<n && !gasit;j++)
                for(l=j+1;l<=n && !gasit;l++)
                    {
                        v[1]=panta(p[i],p[j]),v[2]=panta(p[i],p[l]),v[3]=panta(p[j],p[l]);
                        sort(v+1,v+4);
                        aux.b=v[1];aux.c=v[2];aux.d=v[3];
                        aux.e=min(dist(p[i],p[j]),min(dist(p[i],p[l]),dist(p[j],p[l])));
                        nr=aria(p[i],p[j],p[l])%mod;
                        for(int d=0;d<Hash[nr].size() && !gasit;d++)
                            if(Hash[nr][d].b==aux.b && Hash[nr][d].c==aux.c &&
                               Hash[nr][d].d==aux.d && Hash[nr][d].e==aux.e)
                               gasit=1;
                        if(!gasit)
                            Hash[nr].push_back(aux);
                    }
        if(gasit)
            g<<"DA\n";
        else
            g<<"NU\n";
        for(i=0;i<mod;i++)
            Hash[i].clear();
    }
    f.close();
    g.close();
    return 0;
}