題意：

? ? ? 有一個(gè)m*m的格子，左下角（0,0）右上角(m-1,m-1),網(wǎng)格里面有兩個(gè)y坐標(biāo)相同的賓館（A,B），每個(gè)賓館里面有一個(gè)餐廳，一共用n個(gè)餐廳，第1,2個(gè)都在賓館里，3,4...在其他位置，你現(xiàn)在要在空余坐標(biāo)上建立一個(gè)自己的餐廳，餐廳必須建立在最有利的位置上，什么樣的位置算是有利的位置？如果你要在C這二個(gè)點(diǎn)建立一個(gè)餐廳，假如你要比D這個(gè)餐廳的位置有利那么你到A賓館里里面的餐廳1的距離比C到這個(gè)賓館的近，或者是到B的也行，只要有一個(gè)比C的近，那么你的位置就比C好，如果當(dāng)前點(diǎn)想建立餐廳，那么必須必所有的餐廳的位置都好才行，問(wèn)一共多有多少個(gè)好的位置。

思路：
? ? ? ?吭了好幾個(gè)小時(shí)了，終于想出來(lái)了，對(duì)于每一個(gè)已經(jīng)有的餐館（包括第一個(gè)和第二個(gè)），他們會(huì)限制兩個(gè)區(qū)域，分別是這兩個(gè)區(qū)域（用右上方這個(gè)點(diǎn)舉例）：
每個(gè)點(diǎn)都有這樣類(lèi)此的以AB連線(xiàn)對(duì)稱(chēng)的兩個(gè)限制區(qū)域，我們把所有區(qū)域疊加起來(lái)，最后剩下的就是可行的區(qū)域，疊加的時(shí)候也很簡(jiǎn)單，我們枚舉x1--x2的所有x,Yu[x]表示x節(jié)點(diǎn)在A(yíng)B連線(xiàn)上方的最小限制值，Yd[x]是下方的最大限制值，Y[x] = minn(Yu[x] - y ,Yd[x] - y)，表示的是在x這個(gè)點(diǎn)的這一豎列的最大非限制距離，然后就是簡(jiǎn)單更新，具體細(xì)節(jié)看下面代碼。




#include<stdio.h>


#define N 66000
#define INF 100000000


int maxx(int x ,int y)
{
? ?return x > y ? x : y;
}


int minn(int x ,int y)
{
? ?return x < y ? x : y;
}


int Yu[N] ,Yd[N] ,Y[N];


int main ()
{
? ?int t ,n ,m ,i ,x ,y ,x1 ,x2 ,y1 ,y2;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d %d" ,&m ,&n);
? ? ? scanf("%d %d" ,&x1 ,&y1);
? ? ? scanf("%d %d" ,&x2 ,&y2);
? ? ? if(x1 > x2) x = x1 ,x1 = x2 ,x2 = x;
? ? ? for(i = x1 ;i <= x2 ;i ++)
? ? ? Yd[i] = -INF ,Yu[i] = INF;
? ? ? for(i = 3 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d" ,&x ,&y);
? ? ? ? ?if(y >= y1) Yu[x] = minn(Yu[x] ,y);
? ? ? ? ?if(y <= y1) Yd[x] = maxx(Yd[x] ,y);
? ? ? }
? ? ? Y[x1] = Y[x2] = 0;
? ? ? for(i = x1 + 1 ;i < x2 ;i ++)
? ? ? Y[i] = minn(Yu[i] - y1 ,y1 - Yd[i]);
? ? ??
? ? ? for(i = x1 + 1 ;i < x2 ;i ++)
? ? ? Y[i] = minn(Y[i-1] + 1 ,Y[i]);
? ? ??
? ? ? for(i = x2 - 1 ;i > x1 ;i --)
? ? ? Y[i] = minn(Y[i+1] + 1 ?,Y[i]);
? ? ??
? ? ? long long Ans = 0;
? ? ? for(i = x1 + 1 ;i < x2 ;i ++)
? ? ? {
? ? ? ? ?if(Y[i])
? ? ? ? ?{
? ? ? ? ? ? Ans ++;
? ? ? ? ? ? Ans += (long long)minn(m - 1 - y1 ,Y[i] - 1);//防止出現(xiàn)INF
? ? ? ? ? ? Ans += (long long)minn(Y[i] - 1,y1);//防止出現(xiàn)INF
? ? ? ? ?}
? ? ? }
? ? ? printf("%lld\n" ,Ans);
? ?}
? ?return 0;
}
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ?
? ?
? ?

總結(jié)

以上是生活随笔為你收集整理的LA4851餐厅（求好的坐标的个数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。