半平面交講解 - N^2寫法

 ps:如果這是第一次接觸半平面交,不要認為它是很個高深的東東.其實以你現在的幾何水準完全能夠YY寫出它.

半平面: 對一條直線,它将整個平面分成了兩部分,對于其中的每一部分.就叫做一個半平面.(這個應該好了解吧)

現在我們要保留其中一個半平面,  可以用向量的左邊,右邊來标記,  還可以用  Ax+By+C 與 0的關系來标記(這裡你千萬别糾結它是在直線上方呢,還是下方,而讓自己糊塗了),對于上面的兩種剖分平面的方式, 你當然還可以用其他的條件,比如:    Ax+By+C  與  10 的關系, 我舉這個例子隻是想說明:

         你隻要給出一個條件就行, 對于該條件必有成立與不成立兩部分,這樣就把整個平面分成了兩部分了.

當然我們一般用的上面的兩種..

廢話說了一大托..

趕緊把這個秒了:

       題目: 給一個凸多邊形,然後給你一個向量,求該向量左邊部分與凸多邊形的交集所形成的多邊形,然後得出該多邊形的點集.

很水吧?不會?再好好想想.......

用這條向量與多邊形的每個點判斷是否在該向量的左邊,每條邊是否與該向量所在的直線産生了交點..

有想法了麼? 相信隻是一些細節沒太清楚了?

其實下面的稍微浏覽下就行了,,,半平面交N^2算法,你會發現真得很水.

半平面交N^2算法:

        對凸多邊形,標明一個方向,,對第i個點判斷是否滿足該 向量的條件,如果滿足,把該點加入點集, 然後看i 到i+1這條線段與那條直線是否有交點.有的話加入就行.

ok! 就完了,,,說的一個大概,,你想想自己會怎麼寫,然後看下下面的寫法,綜合一下,你就搞定了

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#define zero(x)((((x)>0?(x):(-(x)))<eps))
using namespace std;
double eps=1e-8;
double pi=acos(-1);
struct P
{
    double x,y;
    void read(){scanf("%lf%lf",&x,&y);}
    P(){}
    P(double x,double y):x(x),y(y){}
    P operator +(const P& p){return P(x+p.x,y+p.y);}
    P operator -(const P& p){return P(x-p.x,y-p.y);}
    P operator /(double d)  {return P(x/d,y/d);}
    P operator *(double d)  {return P(x*d,y*d);}
    P rot(double th){return P(x*cos(th)-y*sin(th),x*sin(th)+y*cos(th));}
    double operator *(const P p){return x*p.y-y*p.x;}
    bool operator !=(const P& p){return (zero(x-p.x)&&zero(y-p.y))==false;}
};
struct Line
{
    P a,b;
    Line(){}
    Line(P a,P b):a(a),b(b){}
};
P tp[305],pp[305];
//pp :記錄最終的點集 , tp:臨時存儲用的
int N;//記錄點集的數目
P ins_seg(P a1,P b1,P a2,P b2)//直線求交
{
    double u=(b1-a1)*(a2-a1);
    double v=(a1-b1)*(b2-b1);
    return (a2 * v + b2 * u ) / ( u + v );
}
void cut(P a,P b)// 用一條有向向量對多變形進行切割,這裡是保留向量的右邊
{
   int dn=0;
   double t1,t2;
   for(int i=0;i<N;i++)// 枚舉每個點
   {
       t1=(b-a)*(pp[i]-a);// 叉積第i個點 
       t2=(b-a)*(pp[(i+1)%N]-a);//叉積第i+1個點
       if(t1<eps)tp[dn++]=pp[i];// 第i個點在向量右邊,加入點集中
       if(t1*t2<-eps)tp[dn++]=ins_seg(a,b,pp[i],pp[(i+1)%N]);// i到i+1的線段與該向量相交（乘積為負，表明兩點不在同一邊，必然相交）
   }
   N=0;
   for(int i=0;i<dn;i++)// 把臨時存儲的點集傳給pp裡面
   if(N==0||pp[N-1]!=tp[i])// 去掉重點..
   pp[N++]=tp[i];
}
           

三道水題:   趕緊寫了,測模闆

POJ 3335 Rotating Scoreboard

http://acm.pku.edu.cn/JudgeOnline/problem?id=3335

POJ 1474 Video Surveillance

http://acm.pku.edu.cn/JudgeOnline/problem?id=1474

POJ 1279 Art Gallery

http://acm.pku.edu.cn/JudgeOnline/problem?id=1279

POJ 3525 Most Distant Point from the Sea （推薦）

http://acm.pku.edu.cn/JudgeOnline/problem?id=3525

備注:題解是白色字型(友善你先思考這個問題)

我當時寫這題反正二了,沒有想到二分,當時用的枚舉第i條,然後切割出在所有邊中,到改邊是最近的點集集合,這裡用角平分線就行切割的,反正我當時寫了很久..自己YY如何求角平分線..

正解二分:關鍵是想到問題等同在該多邊形内放一個最大的圓,求半徑是多少,餘下的你懂的..

POJ 1755 Triathlon （推薦）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1755

備注:題解白色字型

這題,我隻想問,你最後過的時候eps取的是多少..反正我跪了..用的 1e-16過的...我同學是 1e-8過的..