题意：给出很多三角形，问某个点存在于k个三角形内部的概率为多少

思路：叉积判断两个三角形是否为内含关系，并可以拿来求三角形面积，从三角形面积大到小和是否为内含关系来建一颗树，最后DFS求出k层三角形的面积-k+1层三角形的面积，最后除以总面积即可。

/** @Date    : 2016-12-12-21.02  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version :  */#include<bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-6;typedef struct str{    double x, y;}pot;struct trg{    str p1, p2, p3;};struct node{    trg tri;    vector son;    int h;};double cross(str &a, str &b){    return a.x*b.y - a.y*b.x;}str creatstr(str &a, str &b){    str x;    x.x = a.x - b.x;    x.y = a.y - b.y;    return x;}int isin(trg &a, trg &b){    str s1 = creatstr(b.p1, a.p1);    str s2 = creatstr(b.p1, a.p2);    str s3 = creatstr(b.p1, a.p3);    double r1 = cross(s1, s2);    double r2 = cross(s2, s3);    double r3 = cross(s3, s1);    double ep1 = fabs(r1);    double ep2 = fabs(r2);    double ep3 = fabs(r3);    if( ((r1 > 0 && r2 > 0 && r3 > 0 )||(r1 < 0 && r2 < 0 && r3 < 0 )||(ep1 < eps || ep2 < eps || ep3 < eps)) != 1)        return 0;    s1 = creatstr(b.p2, a.p1);    s2 = creatstr(b.p2, a.p2);    s3 = creatstr(b.p2, a.p3);    r1 = cross(s1, s2);    r2 = cross(s2, s3);    r3 = cross(s3, s1);    ep1 = fabs(r1);    ep2 = fabs(r2);    ep3 = fabs(r3);    if( ((r1 > 0 && r2 > 0 && r3 > 0 )||(r1 < 0 && r2 < 0 && r3 < 0 )||(ep1 < eps || ep2 < eps || ep3 < eps)) != 1)        return 0;    s1 = creatstr(b.p3, a.p1);    s2 = creatstr(b.p3, a.p2);    s3 = creatstr(b.p3, a.p3);    r1 = cross(s1, s2);    r2 = cross(s2, s3);    r3 = cross(s3, s1);    ep1 = fabs(r1);    ep2 = fabs(r2);    ep3 = fabs(r3);    if( ((r1 > 0 && r2 > 0 && r3 > 0 )||(r1 < 0 && r2 < 0 && r3 < 0 )||(ep1 < eps || ep2 < eps || ep3 < eps)) != 1)        return 0;    else return 1;}double calarea(trg &a){    str s1 = creatstr(a.p1, a.p2);    str s2 = creatstr(a.p2, a.p3);    double siz = fabs(cross(s1 , s2)) / 2.00000;    return siz;}node* insertT(node *h, trg &a){    node *t;    if(h == NULL)//到叶子时返回    {        t = new node;        t->tri = a;        t->h = 0;        return t;    }    for(int i = 0; i < h->son.size(); i++)    {        t = h->son[i];        if(isin(t->tri, a))        {            h->son[i] = insertT(t, a);  //递归建树            h->son[i]->h = h->h + 1;            return h;        }    }    int p = h->son.size();    h->son.PB(insertT(NULL, a));    h->son[p]->h = h->h + 1;    return h;}double dfs(node *h, int k){    if (h == NULL)        return 0;    if (h->h < k)    {        double sum = 0;        for (int i = 0; i < h->son.size(); i++)            sum += dfs(h->son[i], k);        return sum;    }    else    {        double ins = 0;        for (int i = 0; i < h->son.size(); i++)            ins += calarea(h->son[i]->tri);        return calarea(h->tri) - ins;    }}int cmp(trg a,  trg b){    return calarea(a) > calarea(b);}int main(){    trg tri[1010];    int n, k;    scanf("%d%d", &n, &k);    for(int i = 1; i <= n; i++)    {        double a, b, c, d, e, f;        scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f);        tri[i].p1.x = a;        tri[i].p1.y = b;        tri[i].p2.x = c;        tri[i].p2.y = d;        tri[i].p3.x = e;        tri[i].p3.y = f;    }    sort(tri + 1, tri + 1 + n, cmp);    tri[0].p1.x = -1000;    tri[0].p1.y = -1000;    tri[0].p2.x = 1000;    tri[0].p2.y = -1000;    tri[0].p3.x = 1000;    tri[0].p3.y = 2000;    node *head = NULL;    head = insertT(head, tri[0]);    for(int i = 1; i <= n; i++)    {        head = insertT(head, tri[i]);    }    double ans = 0;    if(k == 0)    {        double t = 0;        for(int i = 0; i < head->son.size(); i++)        {            t += calarea(head->son[i]->tri);        }        ans = 10000 - t;    }    else ans = dfs(head, k);    ans /= 10000.000;    printf("%.5lf\n", ans);    return 0;}

vijos 1288 箱子游戏 计算几何