1877ワイヤレスネットワーク送信機アドレス

1855 ワード

ProblemD:ワイヤレスネットワーク送信機アドレスTime Limit:1 Sec Memory Limit:128 MB
Submit: 27  Solved: 19
[ Submit][ Status][ Web Board]
Description
(wireless.cpp/c/pas)
【問題の説明】
スマートフォンの普及に伴い、無線網に対する需要が高まっている.ある都市は都市内の公共の場所を無線網で覆うことにした.
この都市のレイアウトは、厳格に平行な129の東西方向の街と129の南北方向の街とで形成されたメッシュ状であり、隣接する平行な街の間の距離は一定値1であると仮定する.東西方向街道は北から南へ0,1,2,128,南北方向街道は西から東へ0,1,2,128の順である.
東西に街道と南北に街道が交差して交差点を形成し、xの南北に街道とyの東西に街道が形成された交差点の座標を(x,y)とする.いくつかの交差点には一定数の公共の場所がある.
政府の財政問題のため、大規模なワイヤレスネットワーク送信機を1つしかインストールできません.この無線ネットワーク送信機の伝播範囲は、この点を中心として、辺長が2*dの正方形である.伝播範囲には正方形の境界が含まれます.
例えば、図は、d=1の無線ネットワーク送信機のカバー範囲の概略図である.
 
現在、政府の関係部門は、伝播パラメータdの無線ネットワーク送信機を設置する準備をしています.都市内で適切な設置場所を見つけて、カバーされている公共の場所が最も多いようにしてほしいです.
 
【入力】
入力ファイル名はwireless.in.
第1行は、無線ネットワーク送信機の伝搬距離を表す整数dを含む.
2行目は、公共の場所がある交差点の数を表す整数nを含む.
次にn行、各行は3つの整数x,y,kを与え、中間は1つのスペースで隔てられ、交差点の座標(x,y)とその交差点の公共場所の数をそれぞれ表す.同じ座標は一度だけ与えられます.
 
【出力】
出力ファイル名はwireless.out.
最大公共場所をカバーできる設置場所のシナリオ数と、カバーできる最大公共場所の数をそれぞれ表す2つの整数を含む行を出力します.
 
【入出力サンプル】
wireless.in
wireless.out
1 2 4 4 10 6 6 20
1 30
 
【データの説明】
100%のデータに対して,1≦d≦20,1≦n≦20,0≦x≦128,0≦y≦128,0≦
暴力的な解法ですね-0-点ごとに立って交差点がエミッタの範囲内に図を描かないと判断します.理解点=3=
#include 
struct road{
    int x,y,num;
}dre[100];
int d,n;
int solve(int i,int j)
{
    int v,sum=0;
    for(v=0;v=i-d&&dre[v].x<=i+d&&dre[v].y>=j-d&&dre[v].y<=j+d)sum=sum+dre[v].num;  //                 
    return sum;
}
int main()
{
    scanf("%d%d",&d,&n);
    int i,j,m=0,max=0;
    for(i=0;imax)max=solve(i,j),m=1;  //        
            else if(solve(i,j)==max)m++;           //     
    }
    printf("%d %d
",m,max); return 0; }