Zhuge Liang's Mines
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 831 Accepted Submission(s): 396
Once, Zhuge Liang sent the arrogant Ma Shu to defend Jie Ting, a very important fortress. Because Ma Shu is the son of Zhuge Liang's good friend Ma liang, even Liu Bei, the Ex. king, had warned Zhuge Liang that Ma Shu was always bragging and couldn't be used, Zhuge Liang wouldn't listen. Shima Yi defeated Ma Shu and took Jie Ting. Zhuge Liang had to kill Ma Shu and retreated. To avoid Shima Yi's chasing, Zhuge Liang put some mines on the only road. Zhuge Liang deployed the mines in a Bagua pattern which made the mines very hard to remove. If you try to remove a single mine, no matter what you do ,it will explode. Ma Shu's son betrayed Zhuge Liang , he found Shima Yi, and told Shima Yi the only way to remove the mines: If you remove four mines which form the four vertexes of a square at the same time, the removal will be success. In fact, Shima Yi was not stupid. He removed as many mines as possible. Can you figure out how many mines he removed at that time?
The mine field can be considered as a the Cartesian coordinate system. Every mine had its coordinates. To simplify the problem, please only consider the squares which are parallel to the coordinate axes.
In each test case:
The first line is an integer N, meaning that there are N mines( 0 < N <= 20 ).
Next N lines describes the coordinates of N mines. Each line contains two integers X and Y, meaning that there is a mine at position (X,Y). ( 0 <= X,Y <= 100)
The input ends with N = -1.
4
状压DP
四个点判断构成与坐标轴平行的正方形:
选任意3个点,枚举3个顶点判断是否可以构成等腰直角三角形,如果可以判断能否与第4个点构成正方形。。。。。。。
#include <iostream>
#include <cstdio> #include <cstring> #include <vector> using namespace std; struct node int dp[1050000],n; bool Judge(int i,int j,int k,int l) |
* This source code was highlighted by YcdoiT. ( style: Codeblocks )