## 1340: [Baltic2007]Escape The problem of escape

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 285  Solved: 133
[Submit][Status][Discuss]

## Description

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 ）.

## Input

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 .

## Output

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.

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

1

## HINT

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

## Source

[Submit][Status][Discuss]

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)
{
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)
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. ...

__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 ...