Codeforces gym 100517（二分，同方向判断） - c++编程基础

TOP

Codeforces gym 100517（二分，同方向判断）

2015-11-21 00:56:59 来源: 作者: 【大中小】浏览:2次

题意：给了一个凸包，按顺时针顺序给点，点数不超过10万，再给了两个不同点，点严格在凸包内，凸包保证没有三点共线，问凸包上有多少对点（pi, pj），满足pi和pj的线段与两个点的线段严格相交，线段间严格相交意思是交点不在端点。
链接：http://codeforces.com/gym/100517 (K题)

解法：设凸包有n个点，将凸包点集p扩大一倍，变为2n个点。枚举前n个点，每次枚举到 i ，在[i+1, i+n-1]内进行二分，找到两个点p1,p2，满足p1和p2是”最靠近” 那两点线段的点。统计下中间个数即可。二分过程中需要进行一种同方向判断，即判断该直线是否在某一个线段”左边”或”右边”，用叉积判断即可。

代码

//Hello. I'm Peter.
//#pragma comment(linker, /STACK:102400000,102400000)
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                   using namespace std; typedef long long ll; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const double eps = 1e-9, pi = acos(-1.0); inline int sgn(double x){ if(fabs(x) < eps) return 0; else return x > 0? 1 : -1; } struct Point{ double x, y; Point(){}; Point(double x1, double y1){x = x1, y = y1;} }; typedef Point Vector; Vector operator + (const Vector a, const Vector b){return Vector(a.x + b.x, a.y + b.y);} Vector operator - (const Vector a, const Vector b){return Vector(a.x - b.x, a.y - b.y);} double operator * (const Vector a, const Vector b){return a.x * b.x + a.y * b.y;} double operator % (const Vector a, const Vector b){return a.x * b.y - a.y * b.x;} Vector operator * (const Vector a, const double b){return Vector(a.x * b, a.y * b);} Vector operator * (const double b, const Vector a){return Vector(a.x * b, a.y * b);} Vector operator / (const Vector a, const double b){return Vector(a.x / b, a.y / b);} bool operator == (const Point a, const Point b){return sgn(a.x - b.x)==0 && sgn(a.y - b.y)==0;} bool operator || (const Vector a, const Vector b){return sgn(a % b)==0;} bool operator / (const Vector a, const Vector b){return sgn(a % b)!=0;} double Length(Vector v){return (double)sqrt((double)(v.x * v.x + v.y * v.y));} double Dis(Point a, Point b){return Length(a - b);} Vector Rotate(Vector v, double rad){return Vector(v.x * cos(rad) - v.y * sin(rad), v.x * sin(rad) + v.y * cos(rad));} double angle(Vector v){return atan2(v.y, v.x);} double angle(Vector a, Vector b){ double ans = angle(a) - angle(b); while(sgn(ans) < 0) ans += 2*pi; while(sgn(ans) >= 2*pi) ans -= 2*pi; return fmin(ans, 2*pi - ans); } double Area_Tri(Point p1, Point p2, Point p3){return 0.5 * fabs((p2 - p1) % (p3 - p1));} double Area_Tri(double a, double b, double c){double p = (a+b+c)/2; return (double)sqrt((double)(p*(p-a)*(p-b)*(p-c)));} struct Line{ Point p; Vector v; Line(){}; Line(Point p1, Vector v1){p = p1, v = v1;} }; Point operator / (const Line a, const Line b){ double t = ((b.p - a.p) % b.v) / (a.v % b.v); return a.p + a.v * t; } double Dis(Point p, Line l){return fabs(l.v % (p - l.p)) / Length(l.v);} double angle(Line a, Line b){double ans = angle(a.v, b.v); return fmin(ans, pi - ans);} struct Seg{ Point p1, p2; Seg(){}; Seg(Point p11, Point p22){p1 = p11, p2 = p22;} }; bool operator / (const Seg a, const Seg b){//need change return sgn((a.p2 - a.p1) % (b.p1 - a.p1)) * sgn((a.p2 - a.p1) % (b.p2 - a.p1)) <= 0 && sgn((b.p2 - b.p1) % (a.p1 - b.p1)) * sgn((b.p2 - b.p1) % (a.p2 - b.p1)) <= 0 ; } bool operator / (const Line a, const Seg b){ return sgn(a.v % (b.p1 - a.p)) * sgn(a.v % (b.p2 - a.p)) <= 0; } bool PointOnSeg(Point p, Seg s){ if((s.p1 - p) / (s.p2 - p)) return false; else if(sgn((s.p1 - p) * (s.p2 - p)) > 0) return false; else return true; } #define N 200010 int n; Point p[N]; Point p1 , p2; Point readPoi(){ int x, y; x = read(), y = read(); return Point(x, y); } void kuoda(){ for(int i = n + 1; i <= n + n; i++){ p[i] = p[i - n]; } } void solve(){ ll ans = 0; for(int i = 1; i <= n; i++){ int l ,r , mid; l = i + 1, r = i + n - 1; Vector v1 = p1 - p[i], v2 = p2 - p[i]; while(l < r){ mid = (l + r) >> 1; Vector v = p[mid] - p[i]; if(sgn(v % v1) <= 0 && sgn(v % v2) <= 0) r = mid; else l = mid + 1; } int tp1 = l; l = i + 1, r = i + n - 1; while(l < r){ mid = (l + r) >> 1; mid++; Vector v = p[mid] - p[i]; if(sgn(v % v1) >= 0 && sgn(v % v2) >= 0) l = mid; else r = mid - 1; } int tp2 = l; if(tp1 != tp2) ans += tp1 - tp2 - 1; } ans >>= 1; cout<
                   
                     0){ for(int i = 1; i <= n; i++) p[i] = readPoi(); p1 = readPoi(); p2 = readPoi(); kuoda(); solve(); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ_1511_Invitation Cards(最短..	下一篇：BNU Training 2015 07 27 题解

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: