AtCoder Regular Contest 076 E Connected?[几何][数据结构优化]-白红宇

AtCoder Regular Contest 076 E Connected?[几何][数据结构优化]

阅读量：7283 次

发布时间：2019-06-30

本文共 2245 字，大约阅读时间需要 7 分钟。

传送门：

Sample Input 1

4 2 30 1 3 11 1 4 12 0 2 2

Sample Output 1

YES

题意：判断是否可以在图内连线使相同数字连接起来。

题解：作图可以发现只要不是两个点都位于矩形边界之上，都一定可以通过各种神奇的扭曲实现连接（总有缝可以钻：））。所以排除所有两点不同时在矩形边界的线段，剩下的只需要保证两点都在边界的线段不相交即可，然而正常判断线段相交方法需要N^2。自己做的时候只会排序后按斜率确定边界是否合法，但是需要判断两点在同一边的线段是否跨越当前线段，非常麻烦。官方题解用了栈处理，按顺时针排序所有线段后（线段两点也按顺时针方向排序），按顺时针遍历每个点，如果是线段起始点，push这个点对应的终止点。如果是线段终止点，检查栈顶是否是这个点，如果不是则当前点线段则和应该出现的点的线段一定相交，具体看代码。

右图遍历到A‘时栈顶应该为B‘，所以不成立。

代码：

1 #define _CRT_SECURE_NO_DEPRECATE 2 #pragma comment(linker, "/STACK:102400000,102400000") 3 #include
     
         4 #include
      
          5 #include
       
           6 #include
        
          7 #include
         
             8 #include
          
            9 #include
           
             10 #include
            
              11 #include
             
              12 #include
              
               13 #include
               
                 14 #include
                
                  15 #include
                 
                   16 #include
                   17 #include
                   
                     18 #include
                    
                     19 #include
                     
                      20 #define pii pair
                      
                       21 #define mod 100000000722 #define mp make_pair23 #define pi acos(-1)24 #define eps 0.0000000125 #define mst(a,i) memset(a,i,sizeof(a))26 #define all(n) n.begin(),n.end()27 #define lson(x) ((x<<1)) 28 #define rson(x) ((x<<1)|1) 29 #define inf 0x3f3f3f3f30 typedef long long ll;31 typedef unsigned long long ull;32 using namespace std;33 int r, c;34 class T {35 public:36 int mode, v, ope;37 bool operator<(const T&a)38 {39 return v < a.v;40 }41 };42 int getnum(int x, int y)43 {44 if (y == 0)45 return x;46 else if (x == 0)47 return r + r + c + c - y;48 else if (x == c)49 return x + y;50 else if (y == r)51 return r + c + c - x;52 else return -1;53 }54 55 vector
                       
                        a;56 stack
                        
                         sve;57 int main()58 {59 ios::sync_with_stdio(false);60 cin.tie(0);61 int i, j, k, m, n;62 int x1, x2, y1, y2;63 cin >> r >> c >> n;64 int tempa, tempb;65 for (int i = 1; i <= n; ++i)66 {67 cin >> y1 >> x1 >> y2 >> x2;68 tempa = getnum(x1, y1);69 tempb = getnum(x2, y2);70 if (tempb == -1 || tempa == -1)continue;71 if (tempb < tempa)swap(tempa, tempb);72 a.push_back({ 1,tempa,tempb });73 a.push_back({ 2,tempb,tempa });74 }75 sort(all(a));76 for (int i = 0; i < a.size(); ++i)77 {78 if (a[i].mode == 1)79 sve.push(a[i].ope);80 else if (sve.top() == a[i].v)81 sve.pop();82 else83 {84 cout << "NO" << endl;85 return 0;86 }87 }88 cout << "YES" << endl;89 return 0;90 }

转载于:https://www.cnblogs.com/Meternal/p/7075904.html

你可能感兴趣的文章