| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:我用点的X^2+Y^2模以一个数,再枚举对角线.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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator