【u217】土地划分

Time Limit: 1 second
Memory Limit: 128 MB

【问题描述】
在Dukeswood这块土地上生活着一个富有的农庄主和他的几个孩子。在他临终时，他想把他的土地分给他的孩子。他有许多农场，每个农场
都是一块矩形土地。他在农场地图上划上一些直线将矩形分成若干块。当他划直线时，他总是从矩形边界上的某一点划到另一个矩形边
界上的点，这条线的结束点将成为下一条线的起始点。他划线时从不会让任三线共点。例如下图是某一种划分结果。

划分的起始点和结束点均以五角星标记。当他完成划分后，他想要数一下划出的土地的块数以确保每个孩子都有一块地。例如，上图中土地
被划分成18块。然而这个庄主由于年迈常会数错，因而他寻求你的帮助。
请写一个程序，输入原来的土地尺寸及线段的位置，输出划分出的土地块数。

【输入格式】

第一行输入地图的宽度w(1<=w<=100)和高度h(1<=h<=100)，均为整数。
第二行输入线段数L(1<=L<=15)。
以下L+1行每行一个整数坐标(Xi,Yi)，庄主划的线段为(Xi,Yi)-(Xi+1,Yi+1)，i=1,2,…,L。当然(Xi,Yi)必定在矩形的边界上。

【输出格式】
对于给定的输入，输出一行仅含一个数，即划分出的土地块数。

【数据范围】

Sample Input1
19 12
8
2 0
6 12
11 0
19 9
17 12
0 7
15 0
11 12
0 10

Sample Output1
18

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u217

【题解】

一开始，如果一条直线都没有；
则平面数为1；

画一条线则平面数递增1；变成2

再划一条线(不与任何直线相交);则平面数再增加;变成3;

如果再划一条线；和之前的1条线相交，则平面数不是增加1而是增加2了；则变成5；

如果这条线变一下，和之前的2条线相交，则平面数变成增加3；则变成6；即

则枚举线段i;再枚举线段1到i-1
总结一下就是，出现一条线段,平面数递增，如果这条线段和之前的线段相交平面数再递增(相交的坐标要在平面内,所以有一个坐标的判断,且不能在边界上。)
已知两条线段相交;
且知道
x0,y0,x1,y1
x2,y2,x3,y3;
相交的那个程序里面有给出交点坐标；
要把那些垂直和横着的情况去掉；

【完整代码】

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

void rel(LL &r)
{
    r = 0;
    char t = getchar();
    while (!isdigit(t) && t!='-') t = getchar();
    LL sign = 1;
    if (t == '-')sign = -1;
    while (!isdigit(t)) t = getchar();
    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
    r = r*sign;
}

void rei(int &r)
{
    r = 0;
    char t = getchar();
    while (!isdigit(t)&&t!='-') t = getchar();
    int sign = 1;
    if (t == '-')sign = -1;
    while (!isdigit(t)) t = getchar();
    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
    r = r*sign;
}

const int MAXN = 16+5;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const double pi = acos(-1.0);

struct abc
{
    int a0,b0,a1,b1;
};


abc xd[MAXN];
int w,h,l;
LL ans = 0;

bool cross(int i,int j)
{
    abc z = xd[i],y = xd[j];
    if (z.a1==z.a0 && y.a1==y.a0) return false;
    if  ((z.b1-z.b0)*(y.a1-y.a0)==(z.a1-z.a0)*(y.b1-y.b0))
        return false;
    else
    {
        double xx,yy;
        double x0 = z.a0,y0 = z.b0,x1 = z.a1,y1= z.b1;
        double x2 = y.a0,y2 = y.b0,x3 = y.a1,y3 = y.b1;
        //- |
        if (y1==y0 && x3==x2)
        {
            xx = x2,yy = y1;
        }
        else//-- --
            if (y1==y0 && y3==y2)
                return false;
            else//| -
                if (x1==x0 && y3==y2)
                {
                    xx = x1,yy = y2;
                }
                else//  -
                    if (y3==y2)
                    {
                        yy = y2;
                        xx = x0+(x1-x0)*(yy-y0)/(y1-y0);
                    }
                    else
                    {
                        yy = ( (y0-y1)*(y3-y2)*x0 + (y3-y2)*(x1-x0)*y0 + (y1-y0)*(y3-y2)*x2 + (x2-x3)*(y1-y0)*y2 ) / ( (x1-x0)*(y3-y2) + (y0-y1)*(x3-x2) );
                        xx = x2 + (x3-x2)*(yy-y2) / (y3-y2);
                    }
        if (0 < xx && xx<w && 0<yy&&yy<h)
            return true;
        return false;
    }
}

int main()
{
    //freopen("F:\\rush.txt","r",stdin);
    rei(w);rei(h);
    rei(l);
    rei(xd[1].a0);rei(xd[1].b0);
    rep1(i,1,l)
    {
        rei(xd[i].a1);rei(xd[i].b1);
        xd[i+1].a0 = xd[i].a1,xd[i+1].b0 = xd[i].b1;
    }
    ans = 1;
    rep1(i,1,l)
    {
        ans++;
        rep1(j,1,i-1)
            if (cross(i,j))
                ans++;
    }
    cout << ans << endl;
    return 0;
}