1340: [Baltic2007]Escape The problem of escape

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 285  Solved: 133


The war criminals tried to escape from prison , They planned in detail how to escape from the prison itself , After escaping from prison, they hope to find cover in a nearby village . village ( Image below B) And prison ( In the picture A) There's a canyon in the middle , This canyon is also guarded by soldiers . The soldiers guarding the canyon sit on sentries and rarely walk around , The observation range of each soldier is 100 rice . The position of the soldiers determines whether the war criminals can pass through the canyon safely , The condition for safe passage is that at any time the nearest soldier to the war criminals is greater than 100 rice . Given the length of the Canyon 、 Width and coordinates of each soldier in the Canyon , Assume that the soldier's position remains unchanged , Please write a program to calculate whether war criminals will not be found by soldiers , Through the Canyon . If not , Then the war criminals need at least a few soldiers to get through the canyon safely ( Whether a soldier is seen by another soldier or not , He can be wiped out ). 


The first line has three integers L、W and N, They represent the length of the canyon 、 Width and number of soldiers . Next N That's ok , Two integers per line Xi and Yi, It means the first one i Two soldiers at the coordinates of the canyon (0 <= Xi <= L, 0 <= Yi <= W), The coordinates are in meters , The coordinates of the southwest corner of the canyon are (0, 0), The coordinates of the northeast corner are (L, W), See above . Be careful : Through the canyon you can get from (0, ys)(0 <= ys <= W) To (L, ye)(0 <= ye <= W), among ys, ye It doesn't have to be an integer .


There is only one line , It's an integer , That is, the number of soldiers that need to be wiped out to get through the canyon safely , If you don't need to destroy any soldiers , The output 0.

Sample Input

130 340 5
10 50
130 130
70 170
0 180
60 260

Sample Output



1 <= W <= 50,000 1 <= L <= 50,000 1 <= N <= 250




Network flow Minimum cut

Just judge whether two soldiers intersect

 #include <bits/stdc++.h>
const int siz = ;
const int inf = ; int L, W, N; int X[siz];
int Y[siz]; int S, T; int hd[siz];
int nt[siz];
int to[siz];
int fl[siz]; inline void add(int u, int v, int f)
static int edge = , init = ; if (init)memset(hd, -, sizeof(hd)), init = ; nt[edge] = hd[u]; to[edge] = v; fl[edge] = f; hd[u] = edge++;
nt[edge] = hd[v]; to[edge] = u; fl[edge] = ; hd[v] = edge++;
} int dep[siz]; inline bool bfs(void)
static int que[siz], l, r;
memset(dep, , sizeof(dep));
dep[que[l = ] = S] = r = ; while (l != r)
int u = que[l++], v; for (int i = hd[u]; ~i; i = nt[i])
if (fl[i] && !dep[v = to[i]])
dep[que[r++] = v] = dep[u] + ;
} return dep[T];
} int cur[siz]; int dfs(int u, int f)
using std::min; if (u == T || !f)
return f; int used = , flow, v; for (int i = cur[u]; ~i; i = nt[i])
if (fl[i] && dep[v = to[i]] == dep[u] + )
flow = dfs(v, min(fl[i], f - used)); used += flow;
fl[i] -= flow;
fl[i^] += flow; if (fl[i])
cur[u] = i; if (f == used)
return f;
} if (!used)
dep[u] = ; return used;
} inline int maxFlow(void)
int maxFlow = , newFlow; while (bfs())
memcpy(cur, hd, sizeof(cur)); while (newFlow = dfs(S, inf))
maxFlow += newFlow;
} return maxFlow;
} inline long long sqr(long long x)
return x * x;
} inline long long dis(int i, int j)
return sqr(X[i] - X[j]) + sqr(Y[i] - Y[j]);
} signed main(void)
scanf("%d%d%d", &L, &W, &N); for (int i = ; i <= N; ++i)
scanf("%d%d", X + i, Y + i); S = , T = * N + ; for (int i = ; i <= N; ++i)
add(i, i + N, );
if (Y[i] <= )add(S, i, inf);
if (Y[i] >= W - )add(i + N, T, inf);
} for (int i = ; i <= N; ++i)
for (int j = ; j <= N; ++j)
if (dis(i, j) <= && i != j)
add(i + N, j, inf); printf("%d\n", maxFlow());

@Author: YouSiki

BZOJ 1340: [Baltic2007]Escape More articles on escape

  1. 【BZOJ-1340】Escape The problem of escape Minimum cut

    1340: [Baltic2007]Escape The problem of escape Time Limit: 5 Sec  Memory Limit: 162 MBSubmit: 264  Solved: 121[Submit] ...

  2. BZOJ 1342: [Baltic2007]Sound Mute problem ( A monotonous queue )

    I started with a RMQ And then T 了 ... Well, the positive solution is a monotonic queue , Maintain two monotonous queues ... ----------------------------------------------------------- ...

  3. BZOJ 1345: [Baltic2007] Sequence problem Sequence

    1345: [Baltic2007] Sequence problem Sequence Time Limit: 5 Sec  Memory Limit: 162 MBSubmit: 1180  Solved: 633[Subm ...

  4. BZOJ 1342: [Baltic2007]Sound Mute problem | Monotonous queue maintenance is a good problem

    subject : to n A digital , A legal interval [l,l+m-1] requirement max-min<=c Output the left end of all legal intervals , If no output NONE Answer key : Monotone queues maintain both maximum and minimum values #include<cst ...

  5. bzoj AC In reverse order

    Search GO explain : Enter the question number to enter the corresponding question directly , To search for topics with numbers , Please put a single quotation mark before the key words Problem ID Title Source AC Submit Y 1000 A+B Problem ...

  6. Objective-C The logic of small and medium-sized monsters

    Study Objective-C It's been a while since we started our object-oriented program , In order to reward their own learning achievements , Write a little monster to reward yourself . stay LOL There are monsters and heroes in it , Next, let's write a class of small monsters . From a little monster's point of view , Monsters have those lines ...

  7. Prison break Season 1-Episode 19: The Key

    Season 1, Episode 19: The Key -Kellerman: WeusedtohaveaGreatDane, Dane: Big Danish dog We used to have a big Dane bigandwild. ...

  8. Prison break Season 1- Episode 18: Bluff

    Season 1, Episode 18: Bluff -Michael: Scofield Scofield Michael Scofield Michael Scofield -Patoshik: ...

  9. Prison break Season 1-Episode 17: J-Cat

    Season 1, Episode 17: J-Cat -Pope: Hey, that's looking good. hi , It looks great You're making some real progres ...

Random recommendation

  1. linux Environment initialization User problem

    linux  Initialize system configuration (centos6) (2013-04-03 13:19:15) Reprint ▼   classification : linux This blog post is transferred from elsewhere , Original address http://zhoualine.iteye. ...

  2. About debugging logs Log

    __VA_ARGS__   Is a macro with variable parameters , This macro with variable arguments is new C99 New in specification , At present, it seems that there is only gcc Support (VC6.0 The compiler for does not support ). Add... In front of the macro ## Is that , When the number of variable parameters is 0 when , there ## ...

  3. C I / O functions and buffers

    # turn Yes C Deep understanding of language input and output streams and buffers C Language buffer ( cache ) Elaboration buffers are also called caches , It's part of the memory space . in other words , A certain amount of storage space is reserved in the memory space , This storage space is used to buffer input or output data , This part is reserved for ...

  4. AJAX-----03 In ancient times ajax

    use iframe Method realization <!DOCTYPE html> <html lang="en"> <head> <meta charset=&qu ...

  5. Flexigrid Example 2 : In situ editor

    occasionally , We want to edit flexigrid The data in . An in-situ editor is needed , Now there's no need to pop up another dialog . I'm going to show you how to do this . I use the jquery-in-place-editor library . Please refer to the official website ...

  6. unknown filesystem type ‘iso9660’ Type problem --Ubuntu

    unknown filesystem type ‘iso9660’ This type of file is not supported by the system , Just update the kernel with the following command : sudo aptitude update sudo aptitude upg ...

  7. HDU - 1205 I NEED A OFFER!

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=1203 The question : The question asks for a offer The maximum probability of , In the example 0.44 = 1-(1-0.2)*(1- ...

  8. How to use Huawei software to develop cloud rapid deployment PHP Website

    Huawei software development cloud is a tool , I've been following since last year , After all, it's Huawei's latest software development tool , Recently, I have been using Huawei software development cloud for development project management , It has online compilation and build . Cloud online code checking and other functions , Compiling saves a lot of physical machines ...

  9. css3 Box related styles

    1.css3 Of display attribute : inline: inline inline-block: You can set width and height inline block: Set to block : <!DOCTYPE html> <html lang=& ...

  10. 【 turn 】Wi-Fi 20mhz and 40mhz What's the difference in bandwidth ?

    One . Wireless network card mode wifi Now there are mainly 802.11a/b/g/n/ac Five modes of wireless network cards : 1.b The maximum rate of 11Mbps, Frequency band 2.4G, bandwidth 22M: 2.a The maximum rate of 54Mbps, Frequency band 5G, bandwidth ...