Poj 2284 Hoj 1890 That Nice Euler Circuit

本题用到平面图的欧拉公式：设平面图的顶点数、边数和面数分别为V,E,F，则V+F-E=2.
1.在求顶点数V的时候，很容易想到的想法是判断线段两两相交，如果两线段相交，则顶点数+1，但是，两顶点可能会重合，所以必须要求出相交点的坐标。然后去掉重复的顶点，即去掉坐标值相同的顶点，那么此时数组的大小就是V。先用sort排序，再用unique去重。
2.在求E的时候，需要对每个V中的顶点做判断，如果点c在线段(a,b)上，不包含端点，那么线段数目+1，求完以后，加上原来的初始化的线段数即可。
3.依据欧拉公式求F。
[cpp]  
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <algorithm>  
using namespace std;  
  
const double eps = 1e-8;  
  
struct Point  
{  
    double x;  
    double y;  
    Point() {}  
    Point(double _x,double _y):x(_x),y(_y) {}  
    friend Point operator + (Point a,Point b)  
    {  
        return Point(a.x+b.x , a.y+b.y);  
    }  
    friend Point operator - (Point a,Point b)  
    {  
        return Point(a.x-b.x , a.y-b.y);  
    }  
};  
  
struct Edge  
{  
    Point a;  
    Point b;  
};  
Edge e[315];  
Point p_temp[315];  
Point p[100000];  
int p_num = 0;  
  
int dcmp(double x)  //三态函数  
{  
    if(fabs(x)<eps)//在一定的精度范围内可认为是0  
        return 0;  
    return x>0?1:-1;  
}  
double det(Point a,Point b)  // 叉积，重载叉积函数  
{  
    return a.x*b.y-a.y*b.x;  
}  
double det(Point a,Point b,Point o)  // 叉积  
{  
    return det(a-o,b-o);  
}  
double det(Point a,Point b,Point c,Point d)  // 叉积  
{  
    return det(b-a,d-c);  
}  
  
double dot(Point a,Point b)  // 点积  
{  
    return a.x*b.x + a.y*b.y;  
}  
double dot(Point a,Point b,Point o)  // 点积  
{  
    return dot(a-o,b-o);  
}  
void intersect(Point a,Point b,Point c,Point d)// 判断线段是否相交  
{  
    int d1 = dcmp( det(a,b,c) );  
    int d2 = dcmp( det(a,b,d) );  
    int d3 = dcmp( det(c,d,a) );  
    int d4 = dcmp( det(c,d,b) );  
    Point temp;  
    //求交点坐标  
    if((d1*d2<0&&d3*d4<0))  
    {  
        double t = ((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x));  
        temp.x = a.x + (b.x - a.x) * t;  
        temp.y = a.y + (b.y - a.y) * t;  
        p[p_num++] = temp;  
    }  
    //c在(a,b)上  
    else if(d1==0&&dcmp(dot(a,b,c))<=0)  
    {  
        temp.x = c.x;  
        temp.y = c.y;  
        p[p_num++] = temp;  
    }  
    //d在(a,b)上  
    else if(d2==0&&dcmp(dot(a,b,d))<=0)  
    {  
        temp.x = d.x;  
        temp.y = d.y;  
        p[p_num++] = temp;  
    }  
    //a在(c,d)上  
    else if(d3==0&&dcmp(dot(c,d,a))<=0)  
    {  
        temp.x = a.x;  
        temp.y = a.y;  
        p[p_num++] = temp;  
    }  
    //b在(c,d)上  
    else if(d4==0&&dcmp(dot(c,d,b))<=0)  
    {  
        temp.x = b.x;  
        temp.y = b.y;  
        p[p_num++] = temp;  
    }  
}  
//从大到小排序  
bool cmp(Point a,Point b)  
{  
    if(a.x - b.x >eps)  
    {  
        return true;  
    }  
    else if(fabs(a.x - b.x)<eps && a.y - b.y >eps)  
    {  
        return true;  
    }  
    return false;  
  
}  
//两点坐标相等  
bool cmp2(Point a,Point b)  
{  
    if(fabs(a.x - b.x) < eps && fabs(a.y - b.y)<eps)  
    {  
        return true;  
    }  
    return false;  
}  
int main()  
{  
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin);  
#endif  
    int n;  
    int num = 0;  
    while(scanf(" %d",&n)!=EOF && n!=0)  
    {  
        num++;  
        p_num = 0;  
        for(int i=1;i<=n;i++)  
        {  
            scanf(" %lf %lf",&p_temp[i].x,&p_temp[i].y);  
        }  
        for(int i=1;i<n;i++)  
        {  
            e[i].a.x = p_temp[i].x;  
            e[i].a.y = p_temp[i].y;  
            e[i].b.x = p_temp[i+1].x;  
            e[i].b.y = p_temp[i+1].y;  
        }  
        n--;  
        int E = n;  
        int V = 0; &nb

补充：软件开发 , C++ ,