Poj 1054 The Trouble some Frog/OpenJudge 2812悩ましいカエル
11712 ワード
1.リンク先：
http://poj.org/problem?id=1054
http://bailian.openjudge.cn/practice/2812
2.タイトル：
総時間制限:
10000 ms
メモリ制限:
65536 kB
説明
韓国には小さなカエルがいます。夜になると、この蛙は田んぼを飛び越えて、稲を踏みます。農民は朝、踏まれた稲を見て、大きな被害をもたらしたカエルの通る道を探しています。カエルは一本の直線に沿って田んぼを飛び越えます。しかもジャンプするたびに距離は同じです。
下図のように田んぼの稲は格子をなし、稲は一つの格子につきます。カエルはいつも田んぼの側から田んぼに飛び込んで、その直線に沿って田んぼを通って反対側から飛び出していきます。
下図のように、多くのカエルが田んぼを通り抜けるかもしれません。カエルの跳ぶたびに、ちょうど一株の水稲を踏み潰しました。いくつかの水稲は複数のカエルに踏まれるかもしれない。もちろん、農民が見たのは図4の中の様子で、図3の直線も見えないし、他の人の家の畑に踏まれた水稲も見えない。
図4によると、農民はカエルが田んぼを通る時の走行経路を作ることができ、水田を通る時に少なくとも3本の水稲を踏んだカエルだけに関心を持っています。このため、カエルの歩く道には少なくとも3本の踏みつけられた稲が含まれています。一方、カエルの歩く道の直線上には、踏みつけられた稲が歩くべき道ではないということもあります。
①1本の走行経路ではない：踏まれた稲が2本しかない。
②走行経路ですが、（2，6）上の水道は含まれていません。
③踏みつけられた稲が3本あるが、この3本の間の距離は同じではない。
カエルの歩く道の中で、最大何粒の水稲が踏まれているかを確認する手順を書いてください。例えば、図4の答えは7です。6行目の水稲は全部カエルの歩く道を構成しています。
入力
標準入力デバイスからデータを読み込みます。最初の行は2つの整数R、Cで、それぞれ水田の水稲の行数と列数を表しています。1≦R、C≦5000。第二行は整数Nで、踏まれた水稲の数を表しています。3≦N≦5000。残りのN行には、1行につき2つの整数があり、それぞれ水稲を踏まれた行番号（1〜R）と列番号（1〜C）があり、2つの整数は1つのスペースで区切られています。また、踏みつけられた稲は一度だけ並べられています。
出力
標準出力装置から整数を出力します。田んぼにカエルの走行経路があれば、最大水稲を含むカエルの走行経路の中の水稲の数を出力します。さもなければ、0を出力します。
サンプル入力
1054
3.考え方：
列挙して、データ量はわりに大きくて、最適化をします。
まず、ステップ数が一番多い可能性があるかどうかを判断します。不可能ならスキップします。判断する必要はありません。
4.コード：
http://poj.org/problem?id=1054
http://bailian.openjudge.cn/practice/2812
2.タイトル：
総時間制限:
10000 ms
メモリ制限:
65536 kB
説明
韓国には小さなカエルがいます。夜になると、この蛙は田んぼを飛び越えて、稲を踏みます。農民は朝、踏まれた稲を見て、大きな被害をもたらしたカエルの通る道を探しています。カエルは一本の直線に沿って田んぼを飛び越えます。しかもジャンプするたびに距離は同じです。
下図のように田んぼの稲は格子をなし、稲は一つの格子につきます。カエルはいつも田んぼの側から田んぼに飛び込んで、その直線に沿って田んぼを通って反対側から飛び出していきます。
下図のように、多くのカエルが田んぼを通り抜けるかもしれません。カエルの跳ぶたびに、ちょうど一株の水稲を踏み潰しました。いくつかの水稲は複数のカエルに踏まれるかもしれない。もちろん、農民が見たのは図4の中の様子で、図3の直線も見えないし、他の人の家の畑に踏まれた水稲も見えない。
図4によると、農民はカエルが田んぼを通る時の走行経路を作ることができ、水田を通る時に少なくとも3本の水稲を踏んだカエルだけに関心を持っています。このため、カエルの歩く道には少なくとも3本の踏みつけられた稲が含まれています。一方、カエルの歩く道の直線上には、踏みつけられた稲が歩くべき道ではないということもあります。
①1本の走行経路ではない：踏まれた稲が2本しかない。
②走行経路ですが、（2，6）上の水道は含まれていません。
③踏みつけられた稲が3本あるが、この3本の間の距離は同じではない。
カエルの歩く道の中で、最大何粒の水稲が踏まれているかを確認する手順を書いてください。例えば、図4の答えは7です。6行目の水稲は全部カエルの歩く道を構成しています。
入力
標準入力デバイスからデータを読み込みます。最初の行は2つの整数R、Cで、それぞれ水田の水稲の行数と列数を表しています。1≦R、C≦5000。第二行は整数Nで、踏まれた水稲の数を表しています。3≦N≦5000。残りのN行には、1行につき2つの整数があり、それぞれ水稲を踏まれた行番号（1〜R）と列番号（1〜C）があり、2つの整数は1つのスペースで区切られています。また、踏みつけられた稲は一度だけ並べられています。
出力
標準出力装置から整数を出力します。田んぼにカエルの走行経路があれば、最大水稲を含むカエルの走行経路の中の水稲の数を出力します。さもなければ、0を出力します。
サンプル入力
6 7
14
2 1
6 6
4 2
2 5
2 6
2 7
3 4
6 1
6 2
2 3
6 3
6 4
6 5
6 7 7
1054
3.考え方：
列挙して、データ量はわりに大きくて、最適化をします。
まず、ステップ数が一番多い可能性があるかどうかを判断します。不可能ならスキップします。判断する必要はありません。
4.コード：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4
5 using namespace std;
6
7 struct STEP
8 {
9 int x;
10 int y;
11 };
12
13 int cmp(const void *a,const void *b)
14 {
15 STEP step1 = *((STEP *)a);
16 STEP step2 = *((STEP *)b);
17 if(step1.x == step2.x) return step1.y - step2.y;
18 else return step1.x - step2.x;
19 }
20
21 int main()
22 {
23 int i,j;
24
25 int r,c;
26 cin>>r>>c;
27
28 int n;
29 cin>>n;
30 STEP *steps = new STEP[n];
31
32 for(i = 0; i < n; ++i)
33 {
34 cin>>steps[i].x>>steps[i].y;
35 }
36 qsort(steps,n,sizeof(STEP),cmp);
37
38 int dx,dy,dx0,dy0,dxk,dyk;
39 int max = 0;
40 int count;
41 for(i = 0;i < n-1; ++i)
42 {
43 for(j = i + 1; j < n; ++j)
44 {
45 dx = steps[j].x - steps[i].x;
46 dy = steps[j].y - steps[i].y;
47
48 dx0 = steps[i].x - dx;
49 dy0 = steps[i].y - dy;
50 if((dx0 >0 && dx0 <= r) && (dy0 > 0 && dy0 <= c)) continue;
51
52 dxk = dx0 + (max + 1) * dx;
53 dyk = dy0 + (max + 1) * dy;
54 if(dxk <= 0 || dxk > r || dyk <= 0 || dyk > c) continue;
55
56 dxk = steps[j].x + dx;
57 dyk = steps[j].y + dy;
58 count = 2;
59 while((dxk >0 && dxk <= r) && (dyk > 0 && dyk <= c))
60 {
61 STEP step;
62 step.x = dxk;
63 step.y = dyk;
64
65 if(bsearch(&step,steps,n,sizeof(STEP),cmp) == NULL) break;
66
67 count++;
68 dxk += dx;
69 dyk += dy;
70 }
71 if(!((dxk >0 && dxk <= r) && (dyk > 0 && dyk <= c)))
72 {
73 if(count > max && count > 2) max = count;
74 }
75 }
76 }
77 cout<<max<<endl;
78
79 delete [] steps;
80 return 0;
81 }