Cod sursa(job #1207581)

Utilizator tudormaximTudor Maxim tudormaxim Data 13 iulie 2014 14:12:07
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
const int MOD = 666013;
const int NM = 1002;
typedef struct lnod{
        int x,y,ind;
        lnod *next;
        }*Nod;
typedef struct P{ int x,y; }Point;
Point a[NM];
string s;
Nod h[MOD];
ifstream in("patrate3.in");
ofstream out("patrate3.out");

bool cmp(const Point &a, const Point &b)
{
     if(a.x!=b.x) return (a.x<b.x);
     else return (a.y<b.y);
}

inline int abs(int x)
{
    return (x<0)?(-x):(x);
}

void add(Nod &q,int x,int y,int ind)
{
     Nod p = new lnod;
     p->x=x;
     p->y=y;
     p->ind=ind;
     p->next=q;
     q=p;
}

int main()
{

    int N,i,j,x,y,l,DX,DY,p1x,p1y,Q,f1,nr=0,semn;

    in>>N; getline(in,s);
    for(i=1;i<=N;++i)
    {
      getline(in,s);
      x=y=0; l=s.size();
      semn=0;
      for(j=0;s[j]!=' ';++j)
        if(s[j]!='.')
        {
          if(s[j]=='-') semn=1;
            else x=(x*10)+(s[j]-'0');
        }
      if(semn) a[i].x=-x; else a[i].x=x;
      semn=0;
      for(++j; j<l;++j)
        if(s[j]!='.')
        {
          if(s[j]=='-') semn=1;
          else y=(y*10)+(s[j]-'0');
        }

      if(semn) a[i].y=-y; else a[i].y=y;
    }

    sort(a+1,a+N+1,cmp);
    for(i=1;i<=N;++i) add(h[abs(a[i].x+a[i].y)%MOD],a[i].x,a[i].y,i);

    for(i=1;i<N;++i)
      for(j=i+1;j<=N;++j)
      {
        DX=a[j].x-a[i].x; DY=a[j].y-a[i].y;
        p1x=a[i].x+DY; p1y=a[i].y-DX;

        Q=(abs(p1x+p1y))%MOD;
        f1=0;
        for(Nod p=h[Q];p;p=p->next)
          if(p->x==p1x && p->y==p1y)
          {
            if(p->ind > i) f1=p->ind;
            break;
          }

        if(f1){
          p1x=a[j].x+DY; p1y=a[j].y-DX;

          Q=(abs(p1x+p1y))%MOD;
          for(Nod p=h[Q];p;p=p->next)
            if(p->x==p1x && p->y==p1y)
              {
                if(p->ind>i)
                    ++nr;
               break;
              }
          }
      }

    out<<nr<<'\n';

 return 0;
}