程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1264 構建凸包判定點求面積

POJ 1264 構建凸包判定點求面積

編輯：C++入門知識

F - SCUD Busters Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 1264

Description

Some problems are difficult to solve but have a simplification that is easy to solve. Rather than deal with the difficulties of constructing a model of the Earth (a somewhat oblate spheroid), consider a pre-Columbian flat world that is a 500 kilometer x 500 kilometer square.
In the model used in this problem, the flat world consists of several warring kingdoms. Though warlike, the people of the world are strict isolationists; each kingdom is surrounded by a high (but thin) wall designed to both protect the kingdom and to isolate it. To avoid fights for power, each kingdom has its own electric power plant.
When the urge to fight becomes too great, the people of a kingdom often launch missiles at other kingdoms. Each SCUD missile (anitary leansing niversal estroyer) that lands within the walls of a kingdom destroys that kingdom's power plant (without loss of life).

Given coordinate locations of several kingdoms (by specifying the locations of houses and the location of the power plant in a kingdom) and missile landings you are to write a program that determines the total area of all kingdoms that are without power after an exchange of missile fire.
In the simple world of this problem kingdoms do not overlap. Furthermore, the walls surrounding each kingdom are considered to be of zero thickness. The wall surrounding a kingdom is the minimal-perimeter wall that completely surrounds all the houses and the power station that comprise a kingdom; the area of a kingdom is the area enclosed by the minimal-perimeter thin wall.
There is exactly one power station per kingdom.
There may be empty space between kingdoms.

Input

The input is a sequence of kingdom specifications followed by a sequence of missile landing locations.
A kingdom is specified by a number N (3 <= N <= 100) on a single line which indicates the number of sites in this kingdom. The next line contains the x and y coordinates of the power station, followed by N-1 lines of x, y pairs indicating the locations of homes served by this power station. A value of -1 for N indicates that there are no more kingdoms. There will be at least one kingdom in the data set.
Following the last kingdom specification will be the coordinates of one or more missile attacks, indicating the location of a missile landing. Each missile location is on a line by itself. You are to process missile attacks until you reach the end of the file.
Locations are specified in kilometers using coordinates on a 500 km by 500 km grid. All coordinates will be integers between 0 and 500 inclusive. Coordinates are specified as a pair of integers separated by white-space on a single line. The input file will consist of up to 20 kingdoms, followed by any number of missile attacks.

Output

The output consists of a single number representing the total area of all kingdoms without electricity after all missile attacks have been processed. The number should be printed with (and correct to) two decimal places.

Sample Input

Sample Output

70.50

題意：給你N個王國，求下凸包，再求面積。給你一些炮彈，問炮彈炸掉的面積。（一個炮彈炸的話，整個王國都被炸了）。

思路：這題一看就是面積嘛，只不過需要判定點在哪個凸包裡面才得取，而且每個凸包的面積只能取一次，因為炸掉的面積重新炸第二次就木有了。

不過與前幾題練習不同的地方就是這裡有很多個凸包，然後我一想，就把vector改成了二維的了……然後逗了……輸入老是運行崩潰，妹妹滴！！！檢查好久也看不出哪個錯啊，而且已經把二維的長度給resize了還出錯，改了一個多小時實在不行了，就看了眼奎神的代碼……暈……就知道自己思想不夠開放了。

干嘛跟vector過不去呢，把結構體開個數組不就解決了嘛！唉……自己還是太弱了，把結構體數組給忘了，哈哈……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define eps 1e-8
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define f(i,a,n) for(i=a;i eps);}
inline double sqr(const double &x){ return x * x;}
inline int gcd(int a, int b){ return !b? a: gcd(b, a % b);}
struct Point
{
    double x, y;
    Point(const double &x = 0, const double &y = 0):x(x), y(y){}
    Point operator -(const Point &a)const{ return Point(x - a.x, y - a.y);}
    Point operator +(const Point &a)const{ return Point(x + a.x, y + a.y);}
    Point operator *(const double &a)const{ return Point(x * a, y * a);}
    Point operator /(const double &a)const{ return Point(x / a, y / a);}
    bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);}
    bool operator == (const Point &a)const{ return sgn(sgn(x - a.x) == 0 && sgn(y - a.y) == 0);}
    friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;}
    friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;}
    friend double dist(const Point &a, const Point &b){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
    void in(){ scanf("%lf %lf", &x, &y); }
    void out()const{ printf("%lf %lf\n", x, y); }
};
struct Poly //多邊形類
{
    //vectora;
    vectorp; //順時針凸包
    vectortb;// 逆時針凸包
    void in(const int &r)
    {
        p.resize(r);  //不早凸包的時候可以把p改為a
        for(int i = 0; i < r; i++) p[i].in();
    }
    //計算多邊形的面積
    double getArea()
    {
        int n = tb.size();  //平常的多邊形就把tb換成a
        double ans=0;
        for(int i = 0; i < n; i++) ans += det(tb[i], tb[(i + 1)%n]);
        return ans / 2;
    }
    //判斷點集是否為凸包(返回m-1==n),或者用凸包點算出凸包頂點tb(本題即是)
    void isCanHull()
    {
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        int n = p.size();
        tb.resize(n * 2 + 5);
        int m = 0;
        for(int i = 0; i < n; i++)
        {
            while(m > 1 && sgn(det(tb[m - 1] - tb[m - 2], p[i] - tb[m - 2])) <= 0)m--;
            tb[m++] = p[i];
        }
        int k = m;
        for(int i = n - 2; i >= 0; i--)
        {
            while(m > k && sgn(det(tb[m - 1] - tb[m -2], p[i] - tb[m - 2])) <= 0)m--;
            tb[m++] = p[i];
        }
        tb.resize(m);
        if(m > 1)tb.resize(m - 1);
        //for(int i = 0; i < m - 1; i++) tb[i].out();
    }

    //判斷點t(圓心)是否在凸包內部，這個是O(logn)的算法
    int isContainOlogn(const Point &t)
    {
        int n = tb.size();
        if(n < 3) return 0;
        Point g = (tb[0] + tb[n / 3] + tb[n * 2 / 3] )/ 3.0;
        int l = 0, r = n;
        while(l + 1 < r)
        {
            int mid = (l + r) >> 1;
            int k = sgn(det(tb[l] - g, tb[mid] - g) );
            int dl = sgn(det(tb[l] - g, t - g) );
            int dr = sgn(det(tb[mid] - g, t - g) );
            if(k > 0)
            {
                if(dl >= 0 && dr < 0) r = mid;
                else l = mid;
            }
            else
            {
                if(dl < 0 && dr >= 0) l = mid;
                else r = mid;
            }
        }
        r %= n;
        int res = sgn(det(tb[l] - t, tb[r] - t));
        if(res >= 0) return 1;
        return 0;
    }
}poly[MM];
double sum=0,a,b;
int n,i,k=0,vis[MM];
int main()
{
    while(sca(n)&&n!=-1)
    {
        poly[k].in(n);
        poly[k++].isCanHull();
    }
    while(~scanf("%lf%lf",&a,&b))
    {
        Point bb(a,b);
        for(i=0;i