投資錢景>買台積電就對了5檔高息股比定存強10倍吉隆坡最便宜行程一覽表晚會結束續攤大腸花 學...
2013-04-20 11:36:29 人氣(169) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][三角形交集][線段交點、射線法、凸包] 11122 - Tri Tri

0
收藏
0
推薦

Problem E
TriTri

Input: Standard Input

Output: Standard Output

 

Given the vertices of two triangles, check whether both of them have any common interior point. No points on the edges or vertices are considered interior to a triangle.

 

Input

Input starts with an integer t (t<= 1000) denoting the number of test cases to follow. Each test case contains 12 integers which are the vertices of the triangles as (x, y) pair. First three pairs are for one triangle and rest of them are for the other one. None of the triangles will be invalid. There is a blank line before each test case. 

Output

For each input, print one line of output. Each line will contain "yes" if there are common interior points between the two triangles, "no" otherwise. See the sample output for exact formatting.

 

Sample Input                               Output for Sample Input

2
 
0 0 2 0 0 2
1 1 3 3 2 3
 
0 0 2 0 0 2
3 0 5 0 4 2

pair 1: no

pair 2: no

 


Problemsetter: Mohammad Sajjad Hossain

Special Thanks: Joachim Wulff

只要交集的面積大於 0 就是 yes, 否則 no.

把所有交點找出來!有一個要特殊處理。

如果某一個三角形在另一個三角形內部的話,利用射線法找頂點是否在另一個三角形內部。

把這些點找出來後,做一次凸包,再算凸包面積。

#include <stdio.h>
#include <algorithm>
#include <math.h>
#define eps 1e-8
using namespace std;
struct Pt {
    double x, y;
    bool operator<(const Pt &a) const {
        if(a.x != x)
            return x < a.x;
        return y < a.y;
    }
};
struct Seg {
    Pt s, e;
};
int inInterval(Seg a, Pt p) {
    return min(a.s.x, a.e.x) <= p.x &&
        p.x <= max(a.s.x, a.e.x) &&
        min(a.s.y, a.e.y) <= p.y &&
        p.y <= max(a.s.y, a.e.y);
}
int onLine(Seg a, Pt p) {
    if(fabs((a.s.x-a.e.x)*(p.y-a.s.y)-
            (a.s.y-a.e.y)*(p.x-a.s.x)) > eps)
        return 0;
    return inInterval(a, p);
}
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double D, Dx, Dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    D = a1*b2 - a2*b1;
    Dx = c1*b2 - c2*b1;
    Dy = a1*c2 - a2*c1;
    if(fabs(D) < eps) // NONE or LINE
        return 0;
    p.x = Dx/D, p.y = Dy/D;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return inInterval(a, p) && inInterval(b, p);
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int convexHull(Pt p[], int n, Pt ch[]) {
    sort(p, p+n);
    int m = 0, i, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0;
    p[n] = p[0];
    int i;
    double area = 0;
    for(i = 0; i < n; i++)
        area += p[i].x*p[i+1].y-p[i].y*p[i+1].x;
    return fabs(area/2);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
int main() {
    int t;
    int i, j, k, l;
    int cases = 0;
    Pt A[10], B[10];
    scanf("%d", &t);
    while(t--) {
        for(i = 0; i < 3; i++)
            scanf("%lf %lf", &A[i].x, &A[i].y);
        for(i = 0; i < 3; i++)
            scanf("%lf %lf", &B[i].x, &B[i].y);
        Pt P[50], CH[50], p;
        Seg a, b, c;
        int cnt = 0;
        for(i = 0; i < 3; i++) {
            if(inPolygon(B, 3, A[i]))
                P[cnt++] = A[i];
            if(inPolygon(A, 3, B[i]))
                P[cnt++] = B[i];
            for(j = 0, k = 2; j < 3; k = j++) {
                a.s = A[j], a.e = A[k];
                b.s = B[j], b.e = B[k];
                if(onLine(b, A[i]))
                    P[cnt++] = A[i];
                if(onLine(a, B[i]))
                    P[cnt++] = B[i];
            }
        }
        for(i = 0, j = 2; i < 3; j = i++) {
            for(k = 0, l = 2; k < 3; l = k++) {
                a.s = A[i], a.e = A[j];
                b.s = B[k], b.e = B[l];
                if(calcIntersection(a, b, p)) {
                    P[cnt++] = p;
                }
            }
        }
        /*for(i = 0; i < cnt; i++) {
            printf("(%.3lf, %.3lf)", P[i].x, P[i].y);
        }
        puts("");*/
        int n = convexHull(P, cnt, CH);
        double area = calcArea(CH, n);
        printf("pair %d: ", ++cases);
        if(area > eps)
            puts("yes");
        else
            puts("no");
        //printf("%lf\n", area);
    }
    return 0;
}

線段交點射線法凸包三角形交集11122Tri Tri
台長:Morris
人氣(169) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 10651 - Pebble Solitaire
此分類上一篇:[UVA][窮舉] 10001 - Garden of Eden

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文