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

所以今天PKU会关板..........

Posted by tangjiming at 2008-10-19 17:55:51
In Reply To:今天第一道题完全是POJ2002,可是偶就是TLE。 Posted by:yogafrank at 2008-10-19 17:03:22
> 不过我用了STL里面的一些东西,感觉也不会超时啊。不甘心,我吧代码贴上来。。。
> 差不多就是HASH + 二分。。。难道是由于STL才超时。。。
> #include <iostream>
> #include <vector>
> #include <algorithm>
> using namespace std;
> 
> const int N = 100;
> typedef struct
> {
> 	int x, y;
> }Point;
> Point points[1000];
> bool flag[N];
> vector <int> hash[N];
> int n;
> 
> bool check( int x1, int y1, int x2, int y2 )
> {
> 	if( binary_search( hash[abs( x1 ) % N].begin(), hash[abs( x1 ) % N].end(), y1 ) == false )
> 		return false;
> 	if( binary_search( hash[abs( x2 ) % N].begin(), hash[abs( x2 ) % N].end(), y2 ) == false )
> 		return false;
> 	return true;
> }
> 
> int main ()
> {
> 	int i, j, count, x1, y1, x2, y2, test;
> 
> //	freopen ("1001.txt", "r", stdin);
> 	scanf( "%d", &test );
> 	while( test-- )
> 	{
> 		memset( flag, false, sizeof( flag ) );
> 		scanf( "%d", &n );
> 		count = 0;
> 		for ( i = 0; i < n; i++ ) //下面取模其实是HASH一个点
> 		{
> 			scanf ( "%d%d", &points[i].x, &points[i].y );
> 			int node = abs( points[i].x ) % N;
> 			hash[node].push_back( points[i].y );
> 			flag[node] = true;
> 		}
> 
> 		for( i = 0; i < N; i++ )
> 			if( flag[i] )
> 				sort( hash[i].begin(), hash[i].end() );
> 
> 		for ( i = 0; i < n; i++ )
> 			for ( j = i + 1; j < n; j++ )
> 			{
> 				x1 = points[i].x;
> 				y1 = points[i].y;
> 				x2 = points[j].x;
> 				y2 = points[j].y;
> 
> 				if ( (x1 + x2 + y1 - y2 ) % 2 != 0 )
> 					continue;
> 				if ( (y1 + y2 + x2 - x1 ) % 2 != 0 )
> 					continue;
> 				if ( (x1 + x2 - y1 + y2 ) % 2 != 0 )
> 					continue;
> 				if ( (y1 + y2 + x1 - x2 ) % 2 != 0 )
> 					continue;
> 
> 				int x3 = ( x1 + x2 + y1 - y2 ) / 2;
> 				int y3 = ( y1 + y2 + x2 - x1 ) / 2;
> 				int x4 = ( x1 + x2 - y1 + y2 ) / 2;
> 				int y4 = ( y1 + y2 + x1 - x2 ) / 2;
> 
> 				if( x3 != x1 && x3 != x2 )
> 					continue;
> 				if( x4 != x1 && x4 != x2 )
> 					continue;
> 				if( y3 != y1 && y3 != y2 )
> 					continue;
> 				if( y4 != y1 && y4 != y2 )
> 					continue;
> 
> 				if ( check ( x3, y3, x4, y4 ) )
> 					count++;
> 			}
> 
> 	    printf ("%d\n", count / 2);
> 
> 		for ( i = 0; i < N; i++ )
> 			if( flag[i] )
> 				hash[i].clear();
> 	}
> 
> 	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