ThreadLocal从源码到使用

最好早接触到ThreadLocal是当读书dianping的Cat-client,当时本着它们不是甚懂得,就寻找了一下,大概了解是同等种缓解线程安全题材的编制。现在再次阅读《实战java高并发程序设计》时,又再次对她有矣双重甚一步的问询。

Gym –
101522A

并发程序很关键的主题就是是缓解多线程安全的题材,最广大的处理办法尽管是引入锁的编制;但是锁使得各个线程对临界区的运效率变差,于是有了一样栽新的笔触,即每个线程独立管理有变量,变量的改动以线程中不时独立的。就好比,以前锁之建制是100只人签到,只生一个签字薄;而现在ThreadLocal是每个人一如既往摆纸。

There are two popular formats for representing a date: day/month/year or month/day/year. For example, today can be
represented as 15/8/2017 or 8/15/2017.

唯独者的场景,只是threadLocal的一个用场景。还生只例,是当市里面倒车。小明去上班而先开公交车在举行地铁,如果老是坐车还进票,那么时间效率特别不同。于是小明作了扳平摆放通用的公交卡,公交车和地铁还可以刷。而小蓝小红吧出如此的公交卡,它们的公交卡彼此之间是独的。这就是ThreadLocal的意!

Sometimes (like on today), using one way or another should pose no
confusion — it is immediately understood that the date is the 15th of
August. On other days, however, the two representations may be
interpreted as two different valid dates. For example, the 7th of August
may be misinterpreted as the 8th of July, since both can be represented
as 7/8/2017 (or 8/7/2017).

因而说,ThreadLocal并无是化解线程共享问题,而是为了化解单个线程内部变量的独立性和参数传递的问题。

We say a date (D, M, Y) is ambiguous if D/M/Y and M/D/Y, when both
interpreted in the day/month/year
format, are different valid dates. For example, (7, 8, 2017) and (8, 7,
2017) are ambiguous, while (15, 8, 2017) and (10, 10, 2017) are
not.

那么她的法则时怎么的啊?

The total number of ambiguous dates in the Gregorian calendar system on
any given year is equal to 12 × 11 = 132.

说白了,就是每个线程自己发一个Map,这个Map采用了线性探测法来存储变量。接下来主要看下代码吧:

Now, suppose that in a hypothetical calendar system, there are M months, where the i-th
month has D[i] days, numbered from 1 to
D[i]. Assume that there are no leap
years.

public T get() {
    Thread t = Thread.currentThread();
    // 获取当前线程的localmap
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        // 用当前的变量作为key查询对象
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null) {
            @SuppressWarnings("unchecked")
            T result = (T)e.value;
            return result;
        }
    }
    // 如果不存在的话,初始化变量
    return setInitialValue();
}

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

You are to carry out a calendar reform, by shuffling the array D[], and your target is to minimize the total
number of ambiguous dates in a calendar year. Specifically, you want to
find a permutation p[1], p[2], …, p[M] of integers 1, 2, …, M, such that the new calendar system,
where the i-th month has D[p[i]] days, has the minimal number of
ambiguous dates. Output that minimal
number.

要害时格外getEntry方法:

Input

private Entry getEntry(ThreadLocal<?> key) {
    // 通过当前key的hashcode与列表的长度做 &操作,判断存储的位置
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];
    if (e != null && e.get() == key)
        return e;
    else
        // 如果不存在的话,进入getEntryAfterMiss方法
        // 这种情况,可能是key被回收掉了;也可能是hash冲突了
        return getEntryAfterMiss(key, i, e);
}
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
            Entry[] tab = table;
            int len = tab.length;
// 这里是典型的线性地址探测法
            while (e != null) {
                ThreadLocal<?> k = e.get();
                if (k == key)
                    return e;
                if (k == null)
                    expungeStaleEntry(i);
                else
                    i = nextIndex(i, len);
                e = tab[i];
            }
            return null;
        }        

The first line of input consists of a single integer M, the number of months in the hypothetical calendar
system.

得小心的凡,ThreadLocal里面的内存结构是这般的:
图片 1
出于key是弱引用,因此在gc的当儿会吃回收掉。所以entry中会含有key为null的值,那么这里会无会见产生内存泄漏也?可以拘留一下expungeStaleEntry法,在发现出value为null的时段,threadlocal会自动扫描其他的元素,看看发生没有起key为null的,如果有的话,一并移除。

The second line of input consists of M integers
D[1], D[2], …, D[M], the original
number of days in the i-th
month.

假若也null,需要清理对应之value:

For all test cases, 1 ≤ M ≤ 105, 1 ≤ D[i] ≤ 105.

private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;

    // expunge entry at staleSlot
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    size--;

    // Rehash until we encounter null
    Entry e;
    int i;
    for (i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        if (k == null) {
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            int h = k.threadLocalHashCode & (len - 1);
            if (h != i) {
                tab[i] = null;

                // Unlike Knuth 6.4 Algorithm R, we must scan until
                // null because multiple entries could have been stale.
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    return i;
}

Output

官方推荐使用private
static修饰,跟Java大神聊了下,总结一下ThreadLocal为什么推荐这样以:

Output a single integer, the minimal number of ambiguous dates after the
calendar reform.

  1. 推荐用private修饰,是勿往外部其他的目标呢能够引用到,防止干扰垃圾回收
  2. 推介下static,我个人的知道是以将对象存储到艺术去(static修饰的变量会蕴藏在方法区),这样虽然其中的Entry是死引用,但鉴于变量在方法区,也无见面当gc的时节给回收掉。<—个人掌握哈,如发生畸形,还求指正

Example

应用

以cat的代码中:

public class DefaultMessageManager extends ContainerHolder implements MessageManager, Initializable, LogEnabled {
    // we don't use static modifier since MessageManager is configured as singleton
    private ThreadLocal<Context> m_context = new ThreadLocal<Context>();

    // 每个线程拥有独立的上下文信息
    private Context getContext() {
        if (Cat.isInitialized()) {
            Context ctx = m_context.get();

            if (ctx != null) {
                return ctx;
            } else {
                if (m_domain != null) {
                    ctx = new Context(m_domain.getId(), m_hostName, m_domain.getIp());
                } else {
                    ctx = new Context("Unknown", m_hostName, "");
                }

                m_context.set(ctx);
                return ctx;
            }
        }

        return null;
    }

    @Override
    public void end(Transaction transaction) {
        Context ctx = getContext();

        if (ctx != null && transaction.isStandalone()) {
            if (ctx.end(this, transaction)) {
                m_context.remove();
            }
        }
    }

Input

12
31 28 31 30 31 30 31 31 30 31 30 31

Output

132

Input

3
5 1 1

Output

0

逻辑题,显然某个月份的天数越多,这个月就应该越靠后。
想通就很容易了,排个序就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))

int main()
{
    int n,a[MAXN];
    ll ans=0,sum;
    scanf("%d",&n);
    FOR(i,1,n)
    scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    ans+=2*min(a[1]-1,n-1);
    FOR(i,2,n)
    {
        if(a[i]>i)
        ans+=2*min(a[i]-i,n-i);
    }
    printf("%lld\n",ans);
}

Gym –
101522C

To boost contestants’ performances in the 20th La Salle – Pui Ching Programming Challenge,
the organizers have bought N robots to cheer
for them. Each robot is supposed to display cheering slogans, letter by
letter.

Unfortunately, due to some technical reasons, the display screen of each
robot can only display one fixed character. Therefore, the organizers
decided to arrange the robots in a row, thus forming a string of N letters (What a waste!). All letters are in
uppercase.

The two hosting schools have abbreviated names LSC and PCMS,
as we all know. Which of the two names appear (as a substring) in the
string more often?

Input

The first and only line of input consists of a string with N uppercase letters.

For all test cases, N ≤ 100.

Output

Let A be the number of occurrences of LSC in the given string.

Let B be the number of occurrences of PCMS in the given string.

If A > B, output LSC.

If A < B, output PCMS.

If A = B, output Tie.

 签到开,直接暴力就好了,不过我给卡了瞬间,似乎是我的编译系统和评测系统不同。

推选个例子for(int
i=1;i<1;i++)在自顿时不会见展开演算,在测评那里就是导致访问越界了。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define useit  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
 
int main()
{
    string s;
    cin>>s;
    int l1=0,l2=0;
    if(s.length()>1)
    FOR(i,2,s.length()-1)
    {
        //cout<<s[i-2]<<s[i-1]<<s[i]<<endl;
        if(s[i-2]=='L'&&s[i-1]=='S'&&s[i]=='C')
        l1++;
    }
    if(s.length()>2)
    FOR(i,3,s.length()-1)
    {
        //cout<<s[i-3]<<s[i-2]<<s[i-1]<<s[i]<<endl;
        if(s[i-3]=='P'&&s[i-2]=='C'&&s[i-1]=='M'&&s[i]=='S')
        l2++;
    }
    if(l1>l2)
    cout<<"LSC"<<endl;
    else if(l1<l2)
    cout<<"PCMS"<<endl;
    else
    cout<<"Tie"<<endl; 
}

 

 

  Gym –
101522D                    

 

The Gregorian calendar is internationally the most widely used civil
calendar. It is named after Pope Gregory XIII, who introduced it in
October 1582.

In the Gregorian calendar, there are 28 days in
February in a common year and 29 days in February
in a leap year. Year Y is a leap year if and
only if Y is a multiple of 400, or Y is a multiple of
4 and is not a multiple of 100.

Percy is curious about the distribution of days of the week of his
birthday in his life. By checking the calendar, he quickly finds that in
the years between 1999 and 2017 (inclusive), his birthday (in case you do not
know, 27 February) appears only twice on both Tuesday and Thursday,
three times on each of the other days of the week.

Percy finds counting the distribution of some days in some consecutive
years really cool, so he decides to invent a way to quickly count the
distribution.

Within 15 minutes, he successfully invented a fast program to do the
calculation for years between 1583 and 2 × 109, inclusive. His program can
answer 5000 queries in 1
second. However, he is not sure if the program works correctly, so he
needs your help. Your task is simple, write your own program to do the
calculation, so that Percy can check his program’s correctness by
comparing the outputs of different queries with your
program.

In this problem, please assume the definition of leap years mentioned
above is true for all years between 1583 and
2 × 109, inclusive.

Input

The first line consists of a single integer, Q,
denotes the number of queries. (1 ≤ Q ≤ 5000)

In the next Q lines, each describes a single
query. The queries are in the format S E
M D, which means you have to calculate the distribution of days of the
week for the D-th day of the M-th month for all years between S and E, inclusive. (1583 ≤ S ≤ E ≤ 2 × 109, the days given are one of the
366 valid
days)

Output

Output Q lines, each answers a query
given.

In each line output 7 integers, the frequencies of days of the weeks in
this order: Sunday, Monday, Tuesday, Wednesday, Thursday, Friday,
Saturday.

The order of answers should follow the order of queries given.

Example

Input

1
1999 2017 2 27

Output

3 3 2 3 2 3 3

Input

2
2017 2017 8 15
2017 2021 2 29

Output

0 0 1 0 0 0 0
0 0 0 0 0 0 1

Input

4
3141 5926 5 3
5897 9323 8 4
2718 2818 2 8
2222 2222 2 22

Output

404 391 403 390 404 396 398
488 488 497 481 497 480 496
15 14 14 15 14 15 14
0 0 0 0 0 1 0

日期模拟,发现400年为一个完整的循环(日期星期闰年状态相同),然后要预处理,建议用一个三维数组存情况,这样子写代码会很轻松。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
int isr(int n)
{
    if(n%4==0&&n%100!=0||n%400==0)return 1;
    else return 0;
}
int da[810][15][35];
//20871
void init()
{
    int k[15],l=6;
    k[1]=31,k[2]=28,k[3]=31,k[4]=30,k[5]=31,k[6]=30;
    k[7]=31,k[8]=31,k[9]=30,k[10]=31,k[11]=30,k[12]=31;
    mst(da);
    FOR(i,0,399)
    {
        FOR(j,1,12)
        {
            if(j==2)
            FOR(t,1,k[j]+isr(i))
            {
                if(l+1==8)l=0;
                da[i][j][t]=++l,da[i+400][j][t]=l;
            }
            else
            FOR(t,1,k[j])
            {
                if(l+1==8)l=0;
                da[i][j][t]=++l,da[i+400][j][t]=l;
            }
        }
    }
}

int main()
{
    int q,y1,y2,m,d,t;
    ll s[10];
    cin>>q;
    init();
    while(q--)
    {
        mst(s);
        scanf("%d%d%d%d",&y1,&y2,&m,&d);
        if(y2-y1>=400)
        {
            t=(y2-y1)/400;
            FOR(i,y1%400,y1%400+399)
            s[da[i][m][d]]+=t;
        }
        y1%=400,y2%=400;
        if(y1>y2) y2+=400;
        FOR(i,y1,y2)
        {
            s[da[i][m][d]]++;
        }
        FOR(i,1,7)
        cout<<s[i]<<" ";
        edl;
    }
}

Gym –
101522H                    

 

“Hit!” is a popular game in ancient Byteland.

The very first version of the game is quite simple: each player picks up
a stone and throws it at a circle drawn on the ground. A player wins if
his/her stone lands inside the circle.

After 20 years of practice, Bitman, a young man living in ancient
Byteland, has mastered the skill of throwing stones – he can throw a
stone at any specific place he wants. With such skill, Bitman plays
“Hit!” without losing a single game. He simply targets every stone at
the center of the circle!

The King of Hackerland hears the story of Bitman and wants to challenge
him with a harder, though still very simple, version of “Hit!”.

In each game, two circles which share a positive common area are drawn
on the ground. In order to win, the player must throw a stone at the
common area of the two circles.

As Bitman had no idea how to target his stone at the common area, he
asks for your help. Given the coordinates of the centers and radii of
the two circles, please tell Bitman the coordinates of any point he can
target at such that he can win the game.

For simplicity, you can consider the landing position of the stone as a
single point.

Input

The input consists of two lines, each describes one circle drawn on the
ground. Each line contains three integers x, y and r, denoting
respectively the x-coordinate, y-coordinate, and the radius of a circle.

All coordinates have their absolute value no more than 100, and 1 ≤ r ≤ 100 for both
circles.

Output

Output two numbers, the x-coordinate and y-coordinate of a point where Bitman can throw his
stone at to win the game.

Your answer will be accepted if for each of the two circles, the point
lies inside the circle or that the distance between the point and the
circle is not greater than 10 - 5.

Example

Input

0 0 3
3 4 3

Output

1.5 2.5

Input

-7 -9 3
-4 -4 5

Output

-6 -7

Note

In the first sample, (1.5, 2.5) is a possible
answer as it lies inside the common area of two circles drawn. Please
note that there exists more than one possible answer in this case. For
example, (2, 2), (1, 2)
and (2.1, 1.87) are also possible
answers.

 

事实上题材对于精度没有生高之要求,求出圆心连线及区区独圆满之交点,再出口这有限单点的中央就能满足精度要求,但眼看书出只坑点,如果并线不跟宏观相交就会见错,需要特判

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double eps=1e-6;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
struct point 
{
    double x,y;
    point() {}
    point(double _a,double _b)
    {
        x=_a;
        y=_b;
    }
};

double distan(point p1,point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

double dist(point p1,point p2)
{
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}


int main()
{
    point a,b,c,d,e;
    double r1,r2,l,s;
    cin>>a.x>>a.y>>r1>>b.x>>b.y>>r2;
    l=distan(a,b);
    if(l<r1||l<r2)
    {
        if(l<r1)
        cout<<b.x<<" "<<b.y<<endl;
        else if(l<r2)
        cout<<a.x<<" "<<a.y<<endl;
    }
    else
    {
        s=l-r2;
        c.x=a.x*l-(a.x-b.x)*s;
        c.y=a.y*l-(a.y-b.y)*s;
        s=l-r1;
        d.x=b.x*l-(b.x-a.x)*s;
        d.y=b.y*l-(b.y-a.y)*s;
        e.x=(c.x+d.x)/2/l;
        e.y=(c.y+d.y)/2/l;
        /*while(dist(a,e)>r1*r1)
        {
            e.x+=(b.x-a.x)*eps;
        }
        while(dist(b,e)>r2*r2)
        {
            e.x-=(b.x-a.x)*eps;
        }*/
        cout<<e.x<<" "<<e.y<<endl;
    }

Gym –
101522I

Arya lives in a magical world. You can view it as a number line.

There are N citizens in total. The i-th citizen have his own house in position i with height H*i*, Noted that H*i* could be non positive, which
means their house is actually built beneath the
horizon.

Arya is the hand of the king and she thinks that the buildings are a bit
out of order. She denote the chaos index of the world as
图片 2.

Noted that h*i* could be equal to zero as the
world is magical.

She feels that the current chaos index of the world is too high. So she
designs to change the world a bit by using her super power.

She could flip a continuous sequence of building, i.e., she could choose
two arbitrary integer L and R, where 1 ≤ L ≤ R ≤ N,
and invert the signs of H*i* for all L ≤ i ≤ R (positive to negative and vice
versa).

As Arya is weak, she would only do this operation exactly once. Arya
wants to minimize the chaos index after the operation. Being a good guy,
help Arya to find the lowest possible chaos index after exactly flipping
one continuous sequence of building.

Input

The first line contains an integer N. (1 ≤ N ≤ 106)

The second line consist of N integers, the
i-th integer is H*i*. ( - 109 ≤ H*i* ≤ 109)

Output

Output consist only one integer in a single line, the lowest possible
chaos index after exactly flipping one continuous sequence of building.

Example

Input

4
1 -2 -3 4

Output

3

Input

5
-3 -2 0 -5 3

Output

10

Note

In the first sample, Arya should flip house 2 to 3, so that the heights
become 1, 2, 3, 4 and the chaos index would be
|2 - 1| + |3 - 2| + |4 - 3| = 3.

|x - y| is the absolute difference between
x and y.

逻辑题,当你发现及选一个区间只会指向少单点起震慑时,答案就很肯定了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e6+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
int n,a[MAXN],l1=0,l2=0,s1=0,s2=0,k;
int main()
{
    ll ans=0;
    scanf("%d%d",&n,&a[1]);
    FOR(i,2,n)
    {
        scanf("%d",&a[i]);
        ans+=abs(a[i]-a[i-1]);
        if(a[i]>0&&a[i-1]<0||a[i]<0&&a[i-1]>0)
        {
            if(l1==0)
            {
                l1=i;
                s1=2*min(abs(a[i]),abs(a[i-1]));
            }
            else
            {
                if(l2==0)
                {
                    l2=i;
                    s2=2*min(abs(a[i]),abs(a[i-1]));
                    if(s2>s1)
                    swap(l1,l2),swap(s1,s2);
                }
                else
                {
                    k=2*min(abs(a[i]),abs(a[i-1]));
                    if(k>s1)
                    l2=l1,s2=s1,l1=i,s1=k;
                    else if(k>s2)
                    l2=i,s2=k;
                }
            }
        }
    }
    printf("%lld\n",ans-s1-s2);
}

 

Gym –
101522K                    

The King of Byteland owns an army of well-trained knights. One day, he
decides to attack Hackerland. Hackerland can be described as a grid with
N rows and M columns.
The cell on the i-th row, j-th column is called cell (i, j) for convenience. The north-west corner is
(1, 1) while the south-east corner is (N, M).

In order to win, the Byteland army must occupy all cells with knights.
Now, the King of Byteland has carefully planned the attack. The attack
can be divided into two phases.

In the first phase, a number of knights are sent to some specific cells
of Hackerland.

After the first phase has ended, the second phase begins. In the second
phase, The knights will start attacking the land of Hackerland. Their
only way to attack is as follows: If at any moment, there are two
knights on the same row or the same column, then all unoccupied cells
between the two knights will be under attack, and more knights will be
immediately sent to occupy these cells. This phase will end when no more
cells can be occupied.

Please note that the knights are not allowed to move once they are sent
to Hackerland.

In the following graph, the cells (2, 7), (4, 3), (5, 7) and (8, 3) are occupied in the first phase.

图片 3

When the second phase starts, the cells between (4, 3) and (8, 3), (2, 7) and (5, 7) are under
attack, and then occupied by other knights. Afterwards, the cells
between (4, 3) and (4, 7),
(5, 3) and (5, 7) will
also be occupied. The second phase will end after this as no more cells
can be occupied.

The attack is currently in the first phase. K
cells of Hackerland are already occupied under the command of the King.
You, the leader of the knights, are going to send some more knights
(possibly none) to some cells of Hackerland of your choice before the
second phase starts.

On one hand, you have to send enough knights to ensure that at the end
of the war, all cells are occupied. On the other hand, you have to send
as few knights as possible to minimize the chance of being discovered by
the army of Hackerland. Your task is to find out the minimum number of
knights to be sent.

Input

The first line contains three integers: N,
M and K. (1 ≤ N, M ≤ 100, 0 ≤ K ≤ N·M)

The next K lines each contains two integers:
x and y, which means a
knight was sent by the King to occupy cell (x, y). (1 ≤ x ≤ N, 1 ≤ y ≤ M)

No any two knights are sent to the same cell.

Output

Output an integer, the minimum number of extra knights to be sent, on a
single line.

Example

Input

1 1 0

Output

1

Input

2 2 0

Output

4

Input

3 3 8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3

Output

0

逻辑题,如果玩过黑白棋就知道四个角是什么地位了,其他的位置不会干扰到角。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))

int main()
{
    int n,m,k,ans,a,b;
    scanf("%d%d%d",&n,&m,&k);
    if(n==1||m==1)
    {
        if(n==m)ans=1;
        else ans=2;
        if(n==1)
        FOR(i,1,k)
        {
            scanf("%d%d",&a,&b);
            if(b==1||b==m)ans--;
        }
        else if(m==1)
        FOR(i,1,k)
        {
            scanf("%d%d",&a,&b);
            if(a==1||a==n)ans--;
        }
    }
    else
    {
        ans=4;
        FOR(i,1,k)
        {
            scanf("%d%d",&a,&b);
            if(a==1&&b==m||a==1&&b==1||a==n&&b==1||a==n&&b==m)ans--;
        }

    }
    printf("%d\n",ans);

}