[UVA] 478 - Points in Figures: Rectangles, Circles, and Triangles

題意:
輸入三種圖形，
再輸入點，判斷該點在哪幾個圖形裡面(不包括邊上)。
r是rectangle 四方形(輸入左上和右下的點)
c是circle 圓形(輸入中心點和半徑)
t是triangle 三角形(輸入三個頂點)

--------------------------------------------------

方法:
四方形:
    只要判斷x是否在四方形的左右兩邊裡面，y是否在四方形的上下兩邊。
圓形:
    判斷點到圓中心的距離是否小於半徑。
三角形:
    該點連接到三角形三個頂點可以切成三個三角形，
    任三點可以形成兩個向量，兩個向量可以形成一個三角形，
    所以!如果三個小三角形面積總和等於原始大三角形面積，則點在三角形內
    另外需要注意的是，其中一個小三角形不能為零(若為零表示點在邊上)。
--------------------------------------------------

/* 20150922
 * hanting
 * UVa 478 - Points in Figures: Rectangles, Circles, and Triangles
 * C++
 */
#include <iostream>
#include <vector>
#include <cstdlib>//fabs
#include <cmath>//sqrt
#include <algorithm>//sort
using namespace std;
#define DISTANCE(a,b) sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
#define VEC(a,b) point(b.x-a.x,b.y-a.y)
#define AREA(a,b) fabs((a.x*b.y-a.y*b.x)/2)
struct point
{
    double x,y;
    point(double _x=0,double _y=0):x(_x),y(_y){}
    friend istream& operator>>(istream& in,point &p)
    {
        in>>p.x>>p.y;
        return in;
    }
    bool operator!=(double d)
    {
        return x!=9999.9 and y!=9999.9;
    }
};
struct rectangle
{
    int id;
    point upLeft,lowRight;
    friend istream& operator>>(istream& in,rectangle &rec)
    {
        in>>rec.upLeft>>rec.lowRight;
        return in;
    }
    bool contain(const point &p)
    {
        return p.x>upLeft.x and p.x<lowRight.x and p.y>lowRight.y and p.y<upLeft.y;
    }
};
struct circle
{
    int id;
    point center;
    double radius;
    friend istream& operator>>(istream& in,circle &cir)
    {
        in>>cir.center>>cir.radius;
        return in;
    }
    bool contain(const point &p)
    {
        return DISTANCE(p,center)<radius;
    }
};
struct triangle
{
    int id;
    point v1,v2,v3;
    friend istream& operator>>(istream& in,triangle &tri)
    {
        in>>tri.v1>>tri.v2>>tri.v3;
        return in;
    }
    bool contain(const point &p)
    {
        double a1,a2,a3;
        a1=AREA(VEC(p,v1),VEC(p,v2));
        a2=AREA(VEC(p,v2),VEC(p,v3));
        a3=AREA(VEC(p,v1),VEC(p,v3));
        return a1 and a2 and a3 and (a1+a2+a3)- AREA(VEC(v1,v2),VEC(v1,v3))<1e-8;
    }
};
int main()
{
    char ch;
    vector<rectangle> rec;
    vector<circle> cir;
    vector<triangle> tri;
    int idN=1;
    while(cin>>ch and ch!='*')
    {
        if(ch=='r')
        {
            rectangle tmp;
            cin>>tmp;
            tmp.id=idN;
            rec.push_back(tmp);
        }
        else if(ch=='c')
        {
            circle tmp;
            cin>>tmp;
            tmp.id=idN;
            cir.push_back(tmp);
        }
        else//if(ch=='t)
        {
            triangle tmp;
            cin>>tmp;
            tmp.id=idN;
            tri.push_back(tmp);
        }
        idN++;
    }

    point p;
    int pointN=1;
    while(cin>>p and p!=9999.9)
    {
        vector<int> ans;
        sort(ans.begin(),ans.end());
        for(int i=0;i<rec.size();i++)
        {
            if(rec[i].contain(p))
            {
                ans.push_back(rec[i].id);
            }
        }
        for(int i=0;i<cir.size();i++)
        {
            if(cir[i].contain(p))
            {
                ans.push_back(cir[i].id);
            }
        }
        for(int i=0;i<tri.size();i++)
        {
            if(tri[i].contain(p))
            {
                ans.push_back(tri[i].id);
            }
        }
        if(ans.size())
        {
            for(int i=0;i<ans.size();i++)
            {
                cout<<"Point "<<pointN<<" is contained in figure "<<ans[i]<<endl;
            }
        }
        else
        {
            cout<<"Point "<<pointN<<" is not contained in any figure"<<endl;
        }
        pointN++;
    }
    return 0;
}