Codeforces 492E Vanya and Field


E. Vanya and Field
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output

Vanya decided to walk in the field of sizen × ncells. The field containsmapple trees, thei-th apple tree is at the cell with coordinates(xi, yi). Vanya moves towards vector(dx, dy). That means that if Vanya is now at the cell(x, y), then in a second he will be at cell. The following condition is satisfied for the vector:, whereis the largest integer that divides bothaandb. Vanya ends his path when he reaches the square he has already visited.

Vanya wonders, from what square of the field he should start his path to see as many apple trees as possible.

Input

The first line contains integersn, m, dx, dy(1 ≤ n ≤ 106,1 ≤ m ≤ 105,1 ≤ dx, dy ≤ n) — the size of the field, the number of apple trees and the vector of Vanya's movement. Nextmlines contain integersxi, yi(0 ≤ xi, yi ≤ n - 1) — the coordinates of apples. One cell may contain multiple apple trees.

Output

Print two space-separated numbers — the coordinates of the cell from which you should start your path.If there are several answers you are allowed to print any of them.

Sample test(s)
input
5 5 2 3
0 0
1 2
1 3
2 4
3 1
output
1 3
input
2 3 1 1
0 0
0 1
1 1
output
0 0
Note

In the first sample Vanya's path will look like:(1, 3) - (3, 1) - (0, 4) - (2, 2) - (4, 0) - (1, 3)

In the second sample:(0, 0) - (1, 1) - (0, 0)

题目给出 gcd( n , dx ) = gcd( n , dy ) = 1 , 意味着(0~n-1)每个数都可以遍历到。

然后从x,y轴方向0坐标开始分别预处理出的n个数。

对于两颗苹果树,如果他们 y坐标到0坐标的距离 与 x坐标到0坐标的距离 两者的差值相同。

那么这两个坐标是来自同一个环的。

扫一遍m个点以后取出最大的就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 2000011 ;
const int M = 1000000 ;
const int inf = 1e9+7;
#define X first
#define Y second

int n , m , dx , dy , x[N] , y[N] ,  cnt[N] , id ;
vector<pii>e;
void test() {
    for( int i = 0 ; i < n ; ++i ) cout << x[i] << ' ' ; cout <<endl ;
    for( int i = 0 ; i < n ; ++i ) cout << y[i] << ' ' ; cout <<endl ;
}
void Run() {

    memset( cnt , 0 , sizeof cnt ) ;
    x[0] = 0 ; id = 1 ; for( int i = dx ; i != 0 ; i = (i+dx)%n ) x[i] = id++;
    y[0] = 0 ; id = 1 ; for( int i = dy ; i != 0 ; i = (i+dy)%n ) y[i] = id++;
//    test();
    e.resize(m);
    for( int i = 0 ; i < m ; ++i ) {
        cin >> e[i].X >> e[i].Y ;
        int disx = ( x[e[i].X] + n ) % n ;
        int disy = ( y[e[i].Y] + n ) % n ;
        cnt[ (disx + n - disy)%n  ] ++ ;
    }
    LL ans = 0 ;
    for( int i = 0; i < n ; ++i ) {
        if( cnt[ans] < cnt[i] ) ans = i;
    }
    cout << ( ans*dx ) % n << " 0"<< endl ;
}
int main()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while( cin >> n >> m >> dx >> dy ) Run();
}
View Code

优质内容筛选与推荐>>
1、IE8下网页中的视频会遮挡住顶层DIV的解决办法
2、Ubuntu 11.10下安装Eclipse
3、luogu2870 [USACO07DEC]最佳牛线,黄金Best Cow Line, Gold
4、标准附件,如果上传了没有保存.怎么检查他是否上传了附件
5、2013-06-02


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn