程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu_1086 You can Solve a Geometry Problem too(計算幾何)

hdu_1086 You can Solve a Geometry Problem too(計算幾何)

編輯：C++入門知識

分析：簡單計算幾何題，相交判斷直接用模板即可。

思路：將第k條直線與前面k-1條直線進行相交判斷，因為題目中不排除多條直線相交於同一個點的重復情況。

代碼：

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-8;
const double PI = acos(-1.0);  //比直接寫3.1415926精確

int sgn(double x)              //三態函數，精確度提高
{
        if(fabs(x) < eps)return 0;
        else return x<0? -1:1;
}

struct Point
{
        double x,y;
		Point(){}
        Point(double _x,double _y)  //帶參構造函數
        {
                x = _x;y = _y;
        }
        Point operator -(const Point &b)const  //點相減
        {
                return Point(x - b.x,y - b.y);
        }
        double operator ^(const Point &b)const  //叉積（外積）
        {
                return x*b.y - y*b.x;
        }
        double operator *(const Point &b)const //點積
        {
                return x*b.x + y*b.y;
        }
        void transXY(double B)            //繞原點旋轉角度B（弧度值），後x,y的變化
        {
                double tx = x,ty = y;        //
                x = tx*cos(B) - ty*sin(B);
                y = tx*sin(B) + ty*cos(B);
        }
};
struct Line
{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e)
        {
                s = _s;e = _e;
        }
        //兩直線相交求交點
        //第一個值為0表示直線重合，為1表示平行，為0表示相交,為2是相交
        //只有第一個值為2時，交點才有意義
    pair operator &(const Line &b)const
    {
        Point res = s;
        if(sgn((s-e)^(b.s-b.e)) == 0)
        {
            if(sgn((s-b.e)^(b.s-b.e)) == 0)
                return make_pair(0,res);//重合
            else return make_pair(1,res);//平行
        }
        double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x += (e.x-s.x)*t;
        res.y += (e.y-s.y)*t;
        return make_pair(2,res);
    }
};
Point ms,me;
Line  ml[120];

//*兩點間距離
double dist(Point a,Point b)
{
    return sqrt((a-b)*(a-b));
}
//*判斷線段相交
bool inter(Line l1,Line l2)
{
    return
    max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
    max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
    max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
    max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
    sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 &&
    sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0;
}

int main()
{
    int n;
    int ans;
    while(scanf(%d,&n),n){
        ans=0;
        for(int i=0;i