算法1
(暴力枚举) $O(n^2)$
对于向右的点,能阻挡他的只能是他右下向上的点,或者是他右边(y相同)和他同向的点
把这些点都找出来,按x升序排序,y降序排,第一个阻挡他就是答案中阻挡他的点
而被他阻挡的也是答案中被他阻挡的(因为是按y降序排的,也就是说这是相同最靠上的点) ;
对于向上的点,由于我们在上一步中已经把 它阻挡向右的点 和 被向右的点阻挡的点 都处理了
剩下的就是不被阻挡或者是被向上的点阻挡的点,而这些阻拦他的点在他上方
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std ;
const int N = 100 ;
int n , ans[N];
bool cmp1(vector<int>a , vector<int> b){
return (a[0] - b[0]) ? a[0] < b[0] : a[1] < b[1] ;
}
bool cmp2(vector<int>a , vector<int> b){
return (a[1] - b[1]) ? a[1] < b[1] : a[0] < b[0] ;
}
int main()
{
cin >> n ;
vector<vector<int>> a(n , vector<int>(4)) ;
for(int i = 0 ; i < n ; i ++ )
{
char op ; int x , y ;
cin >> op >> x >> y ;
//存坐标, 方向 1向上、0向右,点的输入顺序
a[i][0] = x , a[i][1] = y , a[i][2] = (op == 'E') , a[i][3] = i ;
}
memset(ans,0x3f,sizeof ans) ;
sort(a.begin(),a.end(),cmp2) ;
//找向右的点右下角的点
for( int i = 0 ; i < n ; i ++ )
{
if( !a[i][2] ) continue ;
vector<vector<int>> b ;
for( int j = 0 ; j < n ; j ++ )
if( a[j][0] > a[i][0] && a[j][1] <= a[i][1] )
b.push_back(a[j]) ;
//按横坐标排序,先阻断的点一定是第一个
sort(b.begin() , b.end() , cmp1 ) ;
for( int j = 0 ; j < b.size() ; j ++ )
{
if( b[j][2] && b[j][1] == a[i][1] )
ans[a[i][3]] = b[j][0] - a[i][0] ;
if( !b[j][2] )
{
int dx = b[j][0] - a[i][0] , dy = a[i][1] - b[j][1] ;
// 向上的点被之前向右的点跟新过,
if( ans[b[j][3]] != 0x3f3f3f3f ) continue ;
if(dx > dy) ans[a[i][3]] = dx ;
if(dx < dy) ans[b[j][3]] = dy ;
}
if( ans[a[i][3]] != 0x3f3f3f3f) break ;
}
}
sort(a.begin(),a.end(),cmp1) ;
for( int i = 0 ; i < n ; i ++ ){
if( a[i][2] ) continue ;
for( int j = 0 ; j < n ; j ++ ){
if( !a[j][2] && a[j][1] > a[i][1] && a[j][0] == a[i][0] )
ans[a[i][3]] = min(ans[a[i][3]] , a[j][1] - a[i][1]) ;
}
}
for( int i = 0 ; i < n ; i ++ )
if( ans[i] == 0x3f3f3f3f) cout << "Infinity\n" ;
else cout << ans[i] << endl ;
return 0 ;
}