The 2018 World Cup was held recently in Russia. Some great soccer countries (e.g., Italy,Netherlands, Chile, USA) did not qualify for this World Cup. These countries have found out thatthey needed more effective passing.
The Problem:
Given the player positions for two teams, determine the minimum number of passes needed to getthe ball from one player to another player. For the purposes of this problem, players do not changeposition, i.e., they do not move.
Player P1 can pass the ball directly to P2 if they are on the same team and no other player is inbetween the two players.
Let’s assume:
P1 and P2 are on the same team
P1, P2, P3 form a line with P3 between P1 and P2
There are no other players on the line formed by P1, P2, P3
Then,
If P3 is on the other team, P1 cannot pass the ball directly to P2.
If P3 is on the same team, P1 can pass the ball to P3 to pass it to P2.
The Input:
The first input line contains an integer, n (2 ≤ n ≤ 11), indicating the number of players on eachteam. The second input line contains 2n integers, providing the (x,y) coordinates for the n playerson Team 1; the first integer on this input line is the x coordinate for Player 1, the second integer isthe y coordinate for Player 1, the third integer is the x coordinate for Player 2, etc. The third inputline provides (in a similar fashion) the (x,y) coordinates for the n players on Team 2. Assume thatall coordinates are integers between 1 and 999 (inclusive) and that all players are on distinctlocations, i.e., no two players occupy the same spot (point).
Assume Player 1 on Team 1 has the ball and wants to pass the ball to Player n on Team 1. Assumethat any player can pass the ball any distance.
The Output:
The output consists of a single integer, indicating the minimum number of passes needed to getthe ball from Player 1 on Team 1 to Player n on Team 1. If it is not possible to get the ball fromPlayer 1 to Player n, print -1.
样例输入1
3
10 15 13 17 10 19
10 17 16 17 13 19
样例输出1
2
样例输入2
5
1 1 3 1 5 1 7 1 9 1
2 1 4 1 6 1 8 1 10 1
样例输出2
-1
样例输入3
3
1 1 5 5 2 2
10 10 50 50 20 20
样例输出3
1
共线判断一下，注意：a,b,c 都是一队且共线的话，那么由a到c，要传两次球。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<int, int>
using namespace std;
int dir[5][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 } ,{ 0,0 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979;
const int mod = 1e9 + 7;
const int maxn = 1e5;
//if(x<0 || x>=r || y<0 || y>=c)
//1000000000000000000
int n;
vector<PII> p1, p2;
bool isBetween(PII p1,PII p2, PII p3)
{
if (p2.first < min(p1.first, p3.first) || p2.first > max(p1.first, p3.first))
return false;
if (p2.second < min(p1.second, p3.second) || p2.second > max(p1.second, p3.second))
return false;
int abx = p2.first-p1.first, aby = p2.second - p1.second;
int acx = p3.first - p1.first, acy = p3.second - p1.second;
return abx * acy - aby * acx == 0;
}
int canPass(int ai, int bi)
{
for (int i = 0; i < n; i++)
{
if (isBetween(p1[ai], p2[i], p1[bi]))
{
return 0;
}
if (i!=ai && i!=bi && isBetween(p1[ai], p1[i], p1[bi]))
{
return 0;
}
}
return 1;
}
int main()
{
cin >> n;
for (int i = 0; i < n;i++)
{
int x, y;
cin >> x >> y;
p1.push_back(make_pair(x, y));
}
for (int i = 0; i < n;i++)
{
int x, y;
cin >> x >> y;
p2.push_back(make_pair(x, y));
}
int dist[11][11];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = canPass(i, j) ? 1 : 1000;
}
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
printf("%d
", dist[0][n - 1] < 1000 ? dist[0][n - 1] : -1);
return 0;
}