(Zj) a074: TOI2011 第五題：畫作問題

http://zerojudge.tw/ShowProblem?problemid=a074

一開始完全不知如何下手

後來就想想，一個三角形，要先有三條線，這三條線互相交錯的解答不能是無解(兩條線平行)或相同(三線共點)，有了這三條線後，再判斷其他的線會不會交在這個三角形上面，就OK了。

(後記) 認真研究複雜度，發現實際上的複雜度為 O(4 * (k/4)^3 * k) = O(k^4)，以k=296的情況來看，應該不會過啊~

#include <iostream>
#include <stdio.h>
#include <assert.h>
using namespace std;

const int MAX_K = 310;
const int INF = 32434259;
int n,m,k;

struct Node {
    double x;
    double y;
    bool real;   //really have answer ???
    bool same;   //the same???
};
//y=ax+b
double a[MAX_K],b[MAX_K];  //yi=aix+bi
Node ans[MAX_K][MAX_K];  //yi=aix+bi 和 yj=ajx+bj 的解 

Node get_ans(int i,int j) {
    Node ret;
    if (i==j) {
        ret.real=false;
        ret.same=false;
    }
    else {
        if (a[i]==a[j]&&b[i]==b[j]) {     //一樣直線 
            ret.real=false;
            ret.same=true;
        }
        else if (a[i]==a[j]&&b[i]!=b[j]) { //斜率一樣but  y潔具不同 
            ret.real=false;
            ret.same=false;
        }
        else if (a[i]==INF) {   //x=???
            ret.x=b[i];
            ret.y=a[j]*b[i]+b[j];
            ret.real=true;
            ret.same=true;
        }
        else if (a[j]==INF) { //x=???
            ret.x=b[j];
            ret.y=a[i]*b[j]+b[i];
            ret.real=true;
            ret.same=true;
        }
        else {
            ret.x=(b[i]-b[j])/(a[j]-a[i]);
            ret.y=a[i]*ret.x+b[i];
            assert(ret.y==a[j]*ret.x+b[j]);
            ret.real=true;
            ret.same=true;
        }
    }
    return ret;
}

void fill_ans(int k) {
    k+=4;
    for (int x=0;k>x;x++) {
        for (int y=0;k>y;y++) {
            ans[x][y]=get_ans(x,y);
        }
    }
}

bool in_range(Node node,double x1,double y1,double x2,double y2) {
    if (x1>x2)swap(x1,x2);
    if (y1>y2)swap(y1,y2);
    if (node.x<x1) return false;
    if (node.x>x2) return false;
    if (node.y<y1) return false;
    if (node.y>y2) return false;
    return true;
}

bool in_range2(Node node,double x1,double y1,double x2,double y2) {
    if (x1>x2)swap(x1,x2);
    if (y1>y2)swap(y1,y2);
    if (node.x<x1) return false;
    if (node.x>x2) return false;
    if (node.y<y1) return false;
    if (node.y>y2) return false;
    return true;
}

bool operator==(const Node& n1, const Node& n2) {
    return (n1.x==n2.x&&n2.y==n1.y);
}

bool check_line(Node node1, Node node2,int i,int k) {
    double x1=node1.x;
    double x2=node2.x;
    double y1=node1.y;
    double y2=node2.y;
    for (int x=0;k>x;x++) {
        if (ans[i][x].real==true) {
            if (ans[i][x]==node1||ans[i][x]==node2) {

            }
            if (ans[i][x]==node1||ans[i][x]==node2) continue;
            if (in_range2(ans[i][x],x1,y1,x2,y2)==true) {

                return false;
            }
        }
    }
    return true;
}

int main () {
    while (scanf("%d %d %d",&n,&m,&k) != EOF) {
        for (int x=0;k>x;x++) {
            int x1,x2,y1,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            if (x1==x2) {  //鉛直縣 
                a[x]=INF;
                b[x]=x1;
            }
            else if (y1==y2) {  //水平線 
                a[x]=0;
                b[x]=y1;
            }
            else {
                a[x]=(y2-y1)/(x2-x1);
                assert(x2-x1!=0);
                b[x]=y2-x2*a[x];
                assert(b[x]==(y1-a[x]*x1));
            }
        }
        //端點 
        a[k]=INF;
        b[k]=0;
        a[k+1]=0;
        b[k+1]=0;
        a[k+2]=INF;
        b[k+2]=n;
        a[k+3]=0;
        b[k+3]=m;
        fill_ans(k);
        k+=4;
        int anss=0;
        for (int p=0;k>p;p++) {
            for (int q=p+1;k>q;q++) {
                Node node[3];
                node[0]=ans[p][q];
                if (node[0].real==false) continue;
                for (int r=q+1;k>r;r++) {   //枚舉which三條作出的三角形 

                    node[0]=ans[p][q];
                    node[1]=ans[p][r];
                    node[2]=ans[q][r];
                    bool check=false;
                    for (int s=0;3>s;s++) {

                        if (node[s].real==false) check=true;
                        else if (in_range(node[s],0,0,n,m)!=true) check=true;
                    }

                    if (check==true) continue;
                    if (node[0]==node[1]) continue;
                    
                    check=check_line(node[0],node[1],p,k);
                    if (check==false) continue;
                    check=check_line(node[1],node[2],r,k);
                    if (check==false) continue;
                    check=check_line(node[0],node[2],q,k);
                    if (check==false) continue;
                    
                    anss++;
                }
            }
        }
        printf("%d\n",anss);
    }
}