Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

注意不要散列出负数就OK

Posted by stupidjohn at 2011-03-23 10:42:56 on Problem 2002
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

struct node
{
	int value;
	int next;
}remain[2000];
int hashtable[1013];
int remaincnt;
inline int trans(int x, int y)
{
	return (x+20000)*40001 + y + 20000;
}
inline int hash(int v)
{
	return v%1013;
}
bool find(int v)
{
	int key = hash(v);
	if(hashtable[key] == -1) return false;
	
	key = hashtable[key];
	while(key != -1 && remain[key].value != v)
		key = remain[key].next;
	if(key == -1) return false;
	else return true;
}
void add(int v)
{
	int key = hash(v);
	remain[remaincnt].value = v;
	remain[remaincnt].next = hashtable[key];
	hashtable[key] = remaincnt++;
}
int x[1003], y[1003];
int main()
{
	int n, cnt;
	int x2, y2, x4, y4;
	while(scanf("%d", &n)!=EOF)
	{
		if(n == 0) break;
		memset(hashtable, -1, sizeof(hashtable));
		remaincnt = 0;
		cnt = 0;
		for(int i =0; i<n; i++)
		{
			scanf("%d %d",&x[i], &y[i]);
			add(trans(x[i], y[i]));
		}
		for(int i =0; i<n-1; i++)
		for(int j = i+1; j<n; j++)
		{
			x2 = (x[i]+x[j]+y[j]-y[i]);
			y2 = (y[i]+y[j]+x[i]-x[j]);
			if((x2&y2)&0x1) continue;
			x2>>=1; y2>>=1;
			if(!find(trans(x2, y2))) continue;
			x4 = (x[i]+x[j]-y[j]+y[i]);
			y4 = (y[i]+y[j]-x[i]+x[j]);
			if((x4&y4)&0x1) continue;
			x4>>=1; y4>>=1;
			if(find(trans(x4, y4))) cnt++;
		}
		
		printf("%d\n", cnt/2);
	}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator