Cod sursa(job #1108162)

Utilizator ion824Ion Ureche ion824 Data 15 februarie 2014 14:14:48
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 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];

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

string s;
Nod h[MOD];

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(){
    ifstream cin("patrate3.in");
    ofstream cout("patrate3.out");
    int N,i,j,x,y,l,DX,DY,p1x,p1y,Q,f1,nr=0,semn;
    
    cin>>N; getline(cin,s);
    for(i=1;i<=N;++i)
    {
      getline(cin,s);
      x=y=0; l=s.length();
      semn=0;
      for(j=0;s[j]!=' ';++j)
        if(s[j]!='.')
        {
          if(s[j]=='-') semn=1;
            else x=(x*10)+(s[j]-'0');
        }
      a[i].x=x * ((semn==1)?(-1):(1)); 
      semn=0; 
      for(++j; j<l;++j)
        if(s[j]!='.')
        {
          if(s[j]=='-') semn=1;
          else y=(y*10)+(s[j]-'0');
        }
          
      a[i].y=y * ((semn==1)?(-1):(1));        
      
                  
    }

    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;
          //f2=0;
          for(Nod p=h[Q];p;p=p->next)
            if(p->x==p1x && p->y==p1y)
              {
                if(p->ind>i)
                    ++nr;
               break;                
              }                             
          }                     
      }
    //nr>>=1;
    cout<<nr<<'\n';
    
 return 0;   
}