首页 > ACM题库 > HDU-杭电 > HDU 4703-Rectangles-计算几何-[解题报告]HOJ
2015
09-17

HDU 4703-Rectangles-计算几何-[解题报告]HOJ

Rectangles

问题描述 :

Group

样例输入:

2
1 1 2 2
2 2 3 3

样例输出:

48
Hint
({1}, {(2,2), (2,2)}) and ({2},{(2,2), (2,2)}) are two different ways.

题意:根据给定的垂直和水平的线段,求能组成的矩形有多少个。

题解:因为题目给的只有垂直和水平的线段,且总线段不超过100.所以我们可以暴力。

1、任选两根水平的线段,若无水平线段可选,结束。否则,转2

2、从所有的垂直线段里,找到和这两根水平线段相交的线段,假设有tmp条。转3

3、对于1步选的两条水平线段,因为有tmp跟垂直线段与其相交,根据推算,可以得知,其能组成的矩形就是(tmp – 1)*tmp / 2 个,将其加进总和里即可。转1

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int  MAX_  = 101;
typedef long long LL;

struct line {
    int x[2],y[2];
} hor[MAX_], ver[MAX_];

int ans;


int main() {
    int Case, n, h,v, tmp, maxh,minh, maxv,minv;
    int x1,y1,x2,y2;
    scanf("%d",&Case);
    while(Case--) {
        scanf("%d",&n);
        ans = 0;
        h = v =  0;
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(y1 == y2) {
                hor[h].x[0] = min(x1,x2);
                hor[h].y[0] = y1;
                hor[h].x[1] = max(x1,x2);
                hor[h++].y[1] = y2;
            } else {
                ver[v].x[0] = x1;
                ver[v].y[0] = min(y1,y2);
                ver[v].x[1] = x2;
                ver[v++].y[1] = max(y1,y2);
            }
        }
        for(int i = 0; i < h - 1; i++) {
            for(int j = i+1; j < h; j++) {
                if(hor[i].x[1] < hor[j].x[0] || hor[i].y[0] == hor[j].y[0]) {
                    continue;
                }
                maxh = min(hor[i].x[1], hor[j].x[1]);
                minh = max(hor[i].x[0], hor[j].x[0]);
                maxv = max(hor[i].y[0], hor[j].y[0]);
                minv = min(hor[i].y[0], hor[j].y[0]);
                tmp = 0;
                for(int k = 0; k < v; k++) {
                    if(ver[k].x[0] >= minh && ver[k].x[0] <= maxh && ver[k].y[0] <= minv && ver[k].y[1] >= maxv){
                        tmp++;
                    }
                }
                ans += (tmp - 1) * tmp /2;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ljd4305/article/details/12234583