Cod sursa(job #434038)

Utilizator mihaionlyMihai Jiplea mihaionly Data 4 aprilie 2010 22:49:48
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <cstdio>
using namespace std;
#define ll long long
#define nmax 1001
#define MOD 666013
FILE *f=fopen("trapez.in","r");
FILE *g=fopen("trapez.out","w");
ll trapeze;
inline ll abs(ll x)
 {
 if(x>0) return x;
 return -x;
 }
struct hash
 {
 ll x1,y1,x2,y2;
 hash *urm;
 };
hash *H[MOD];
void add(hash *&h,ll x1,ll y1,ll x2,ll y2)
 {
 hash *p=new hash;
 p->x1=x1;
 p->y1=y1;
 p->x2=x2;
 p->y2=y2;
 p->urm=h;
 h=p;
 }
struct Punct
 {
 ll x,y;
 };
Punct P[nmax];
int n;
int cmmdc(ll a,ll b)
 {
 if(b==0) return (a%MOD);
 return cmmdc(b,a%b);
 }
bool equal(hash *p,int a5,int a6,int a7,int a8)
 {
 return ((p->x1==a5)&&(p->y1==a6)&&(p->x2==a7)&&(p->y2==a8));
 }
void verify(int x1,int y1,int x2,int y2)
 {
 int ind,cm;
 ll x,y;
 cm=cmmdc(abs(y2-y1),abs(x2-x1));
 y=abs(y2-y1)/cm+1;
 x=abs(x2-x1)/cm+1;
 ind=(((x*y)%MOD+(1<<(((x%10)+(y%10))%10)))%MOD);
 hash *ax,*z;
 if(equal(H[ind],x1,y1,x2,y2))
  {
  ax=H[ind];
  z=H[ind];
  ax=ax->urm;
  H[ind]=ax;
  delete z;
  }
 for(hash *p=H[ind];p!=NULL;p=p->urm)
  {
  if(p->urm&&equal(p->urm,x1,y1,x2,y2))
   {
   ax=p;
   z=p->urm;
   ax->urm=p->urm->urm;
   p=ax;
   delete z;
   }
  if((y2-y1)*(p->x2-p->x1)==(p->y2-p->y1)*(x2-x1))
   ++trapeze;
  }
 }
int main()
 {
 int i,j,cm;
 ll x,y;
 fscanf(f,"%d",&n);
 for(i=1;i<=n;i++) fscanf(f,"%lld %lld",&P[i].x,&P[i].y);
 for(i=1;i<n;i++)
  for(j=i+1;j<=n;j++)
   {
   cm=cmmdc(abs(P[i].y-P[j].y),abs(P[i].x-P[j].x));
   y=abs(P[i].y-P[j].y)/cm+1;
   x=abs(P[i].x-P[j].x)/cm+1;
   x=(((x*y)%MOD+(1<<(((x%10)+(y%10))%10)))%MOD);
   add(H[x],P[i].x,P[i].y,P[j].x,P[j].y);
   }
 for(i=1;i<n;i++)
  for(j=i+1;j<=n;j++)
   verify(P[i].x,P[i].y,P[j].x,P[j].y);
 fprintf(g,"%lld",trapeze);
 return 0;
 }