2014
03-23

# Precious

Gollum is finding his Precious. The precious is hiding in a magic maze. The maze can be considered as a simple polygon. Some vertexes of the polygon are doors that can only allow Gollum to get in, and the other doors can only allow Gollum to get out.
Gollum doesn’t know that restrict, he choose a door to get in, and choose a door to get out after he has got his precious. Gollum hasn’t learned math, so we believe that Gollum choose the door randomly, that means if there are n doors, the probability of a door chose by Gollum is 1/n.
There is a monster in the maze, and if Gollum stay in the maze more than m minutes, the monster will wake up and eat Gollum. Gollum can move one unit distance by one minute.
We want to know the probability that Gollum got his precious.

The input consists of multiply test cases. The first line of each test case contains two integers, n (3 <= n <= 100), m (0 <= m <= 10000), where n is the number of vertexes of the maze, and m is the time limit. The next n lines represent the maze, each line contains a coordinate, x, y (-10000 <= x, y <= 10000) and a DoorType. If DoorType equals to -1, then you can get in from this vertex; if DoorType equals to 0, then it’s not a door; if DoorType equals to 1, then you can get out from this vertex. The last line of each test case is a coordinate, indicating the location of the precious. You can assume that the precious is always in the maze.
The last test case is followed by a line containing two zeros, which means the end of the input.

The input consists of multiply test cases. The first line of each test case contains two integers, n (3 <= n <= 100), m (0 <= m <= 10000), where n is the number of vertexes of the maze, and m is the time limit. The next n lines represent the maze, each line contains a coordinate, x, y (-10000 <= x, y <= 10000) and a DoorType. If DoorType equals to -1, then you can get in from this vertex; if DoorType equals to 0, then it’s not a door; if DoorType equals to 1, then you can get out from this vertex. The last line of each test case is a coordinate, indicating the location of the precious. You can assume that the precious is always in the maze.
The last test case is followed by a line containing two zeros, which means the end of the input.

12 4
-2 -1 -1
-1 -1 -1
-1 -2 -1
1 -2 -1
1 -1 -1
2 -1 -1
2 1 1
1 1 1
1 2 1
-1 2 1
-1 1 1
-2 1 1
0 0
0 0

0.138888889

1. 刚看。。。看了前面，这不是跟电影（环太平洋）感觉一样吗？都是国家为了抵御外星生物，狂妄自大，盖了好多围墙，结果抵不住，后来就主人公，逐渐成为英雄和小伙伴们一起战斗，对抗外星生物。。。但是是电影。 话说，这两个谁先出的谁后出的啊？？？

2. 刚看。。。看了前面，这不是跟电影（环太平洋）感觉一样吗？都是国家为了抵御外星生物，狂妄自大，盖了好多围墙，结果抵不住，后来就主人公，逐渐成为英雄和小伙伴们一起战斗，对抗外星生物。。。但是是电影。 话说，这两个谁先出的谁后出的啊？？？

3. 刚看。。。看了前面，这不是跟电影（环太平洋）感觉一样吗？都是国家为了抵御外星生物，狂妄自大，盖了好多围墙，结果抵不住，后来就主人公，逐渐成为英雄和小伙伴们一起战斗，对抗外星生物。。。但是是电影。 话说，这两个谁先出的谁后出的啊？？？

4. 刚看。。。看了前面，这不是跟电影（环太平洋）感觉一样吗？都是国家为了抵御外星生物，狂妄自大，盖了好多围墙，结果抵不住，后来就主人公，逐渐成为英雄和小伙伴们一起战斗，对抗外星生物。。。但是是电影。 话说，这两个谁先出的谁后出的啊？？？

5. 刚看。。。看了前面，这不是跟电影（环太平洋）感觉一样吗？都是国家为了抵御外星生物，狂妄自大，盖了好多围墙，结果抵不住，后来就主人公，逐渐成为英雄和小伙伴们一起战斗，对抗外星生物。。。但是是电影。 话说，这两个谁先出的谁后出的啊？？？

6. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

7. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}