EOJ Monthly 2019.7 (based on July Selection) D. 求和公式

今天药忘吃喽~ 2021-11-06 01:44 146阅读 0赞

**[https://acm.ecnu.edu.cn/contest/191/problem/D/][https_acm.ecnu.edu.cn_contest_191_problem_D]**

**①两个直线分开考虑，一个是y=x 另一个是y = n-1-x**  
**②考虑直线是否经过两个平行边穿过了矩形还是只是一个角**  
**③矩形可能退化成为一个线段**  
**④需要用到函数判断两个点是否在直线的同一侧，注意可能超过LL范围**  
**⑤n分奇偶分别进行讨论，奇数的时候需要知道矩形过不过两个直线的中心位置如果是要减去1**

#include <iostream>
    #include <stdio.h>
    #include <string>
    #include <vector>
    #include <math.h>
    #include <stdlib.h>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    typedef long long LL;
    LL n,q;
    
    struct point{ 
        LL x;
        LL y;
        point(LL x,LL y){ 
            this->x = x;
            this->y = y;
        }
    };
    
    //是否在y=x同侧
    //大于0就是同侧 小于零是异测 等于零就是一个点在线上
    LL isSameyx(point a,point b){ 
        LL a1 = 1;
        LL a2 = 1;
        if( a.x-a.y < 0){ 
            a1 = -1;
        }else if(a.x-a.y == 0){ 
            a1 = 0;
        }
    
        if( b.x-b.y < 0){ 
            a2 = -1;
        }else if(b.x-b.y == 0){ 
            a2 = 0;
        }
        return a1*a2;
    }
    
    //是否在y=-x+n-1同侧
    LL isSameyxn1(point a,point b){ 
    
        LL a1 = 1;
        LL a2 = 1;
        if( a.x+a.y-n+1 < 0){ 
            a1 = -1;
        }else if( a.x+a.y-n+1 == 0){ 
            a1 = 0;
        }
    
        if( b.x+b.y-n+1 < 0){ 
            a2 = -1;
        }else if( b.x+b.y-n+1 == 0){ 
            a2 = 0;
        }
        return a1*a2;
    }
    
    LL baoCnt(LL a,LL b,LL c,LL d){ 
        LL cnt = 0;
        for(int i = a ;i<= c;i ++){ 
            for(int j = b;j <= d;j++){ 
                if( i==j || i+j==n-1){ 
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    LL myAbs(LL a){ 
        if(a<0){ 
            a = -a;
        }
        return a;
    }
    
    LL myCnt(LL a,LL b,LL c,LL d){ 
            point A(a,b);
            point C(c,d);
            point B(c,b);
            point D(a,d);
            LL cntxy = 0;
            LL cntxyn1 = 0;
            
            if( A.x == C.x || A.y == C.y) { 
    
                if( isSameyx(A,C) <= 0 ){ 
                    cntxy =1;
                }else if(isSameyx(A,C) > 0){ 
                    cntxy  = 0;
                }
    
                if( isSameyxn1(A,C) <= 0 ){ 
                    cntxyn1 = 1;
                }else if(isSameyxn1(A,C)>0){ 
                    cntxyn1  = 0;
                }
    
            }else{ 
                if( isSameyx( B,D)==0 ){ 
                    cntxy = 1;
                }else if( isSameyx( B,D) > 0 ){ 
                    cntxy = 0;
                }else{ 
                    if( (isSameyx( A, B) >=0 && isSameyx(C, D) >= 0) || (isSameyx( A, D) >=0 && isSameyx(C, B)>=0 ) ){ 
                        cntxy = min( myAbs( C.x - A.x ),myAbs( C.y - A.y) ) + 1;
                    }else if( isSameyx( B,C) < 0){ 
                        cntxy = myAbs(B.x - B.y) + 1;
                    }else if( isSameyx( A,D) < 0 ) { 
                        cntxy = myAbs(D.x - D.y) + 1 ;
                    }
                }
    
                if( isSameyxn1( A, C) == 0 ){ 
                    cntxyn1 = 1;
                }else if(isSameyxn1( A,C) > 0){ 
                    cntxyn1 = 0;
                }else{ 
                    if( (isSameyxn1( A, B) >=0 && isSameyxn1(C, D) >= 0) || (isSameyxn1( A, D) >=0 && isSameyxn1(C, B)>=0 )){ 
                        cntxyn1 = min( myAbs(C.x - A.x),myAbs( C.y - A.y )) + 1;
                    } else if( isSameyxn1( A, D) < 0 ){ 
                        cntxyn1 = myAbs( n-1-A.x - A.y) + 1;
                    }else if( isSameyxn1( B, C) < 0 ){ 
                        cntxyn1 = myAbs( n-1-C.x - C.y) + 1;
                    }
                }
    
            }
            if( n%2 == 0 ){ 
    
                return cntxy+cntxyn1 ;
            }else{ 
                if( A.x <= n/2 && A.y <= n/2 && C.x >= n/2 && C.y >= n/2 ){ 
                    return cntxy+cntxyn1-1 ;
                }else{ 
                    return cntxy+cntxyn1 ;
                }
            }
    
    }
    
    int main()
    { 
        //freopen("test.txt","r",stdin);
        scanf("%lld%lld",&n,&q);
        LL a,b,c,d;
    
        for(LL i=0;i<q;i++){ 
            scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
            cout<<myCnt(a,b,c,d)<<endl;
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

[https_acm.ecnu.edu.cn_contest_191_problem_D]: https://acm.ecnu.edu.cn/contest/191/problem/D/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20211104/89a899ed4cc44665a7c860fb002447ab.png