BZOJ 1132 POI 2008 Tro 計算幾何

BZOJ 1132 POI 2008 Tro 計算幾何

題目大意：給出平面上的一些點，問這些點中的任意三個點組成的三角形的面積和是多少。

思路：看數據范圍只算法系列。由於每個三角形有三個頂點，因此暴力的話應該是O(n^3)的時間復雜度，很明顯超時了，但是我們只需要將它優化到O(n^2logn)就可以解決了。

好吧，剩下的隨便猜一猜，比如O(n^2)的枚舉，然後剩下的logn什麼也干不了。。。

再比如O(n)的枚舉，然後剩下O(nlogn)排序。。。

好像有戲啊。。

枚舉每一個點，計算以這個點為坐標原點，在第一象限的所有點與原點組成的三角形的面積和。計算面積可以用叉積，但是這樣算和暴力枚舉有什麼區別？

利用叉積的性質，我們簡單的推倒一下。設原點為O，枚舉到的兩個點為AB，向量OA = (x1,y1),向量OB = (x2,y2)，則

S-OAB = |x1 * y2 - y2 * x2|

對於固定的一個點A來說，線段OA與其他所有點的面積和就是ΣS = x1 * Σy2 - y1 * Σx2

但是這需要滿足面積不能為負數。只需要按照極角或者斜率排序一下就可以避免負數了。這樣正好是O(n^2logn)

CODE：

#include 
#include 
#include 
#include 
#define INF 0x7f7f7f7f
#define MAX 3010
using namespace std;
 
struct Point{
    int x,y;
    double slope;
     
    Point(int _ = 0,int __ = 0):x(_),y(__) {}
    bool operator <(const Point &a)const {
        if(x == a.x)    return y < a.y;
        return x < a.x;
    }
    Point operator -(const Point &a)const {
        return Point(x - a.x,y - a.y);
    }
    void Read() {
        scanf("%d%d",&x,&y);
    }
}point[MAX],now;
 
int points;
 
bool cmp(const Point &a,const Point &b)
{
    return a.slope < b.slope;
}
 
inline long long Calc(int p,int cnt)
{
    static Point temp[MAX];
    now = point[p];
    memcpy(temp + 1,point + p + 1,sizeof(Point) * cnt);
    for(int i = 1; i <= cnt; ++i) {
        temp[i] = temp[i] - now;
        if(!temp[i].x)  temp[i].slope = INF;
        else    temp[i].slope = (double)temp[i].y / (double)temp[i].x;
    }
    sort(temp + 1,temp + cnt + 1,cmp);
 
    static long long sum_x[MAX],sum_y[MAX],re;
    re = 0;
    memset(sum_x,0,sizeof(sum_x));
    memset(sum_y,0,sizeof(sum_y));
    for(int i = cnt; i; --i) {
        sum_x[i] = sum_x[i + 1] + temp[i].x;
        sum_y[i] = sum_y[i + 1] + temp[i].y;
    }
    for(int i = 1; i < cnt; ++i) {
        re += temp[i].x * sum_y[i + 1];
        re -= temp[i].y * sum_x[i + 1];
    }
    return re;
}
 
int main()
{
    cin >> points;
    for(int i = 1; i <= points; ++i)
        point[i].Read();
    sort(point + 1,point + points + 1);
    long long ans = 0;
    for(int i = 1; i <= points; ++i)
        ans += Calc(i,points - i);
    bool flag = ans&1;
    printf("%lld.%d\n",ans >> 1,(int)flag ? 5:0);
    return 0;
}