poj 3168 Barn Expansion

Barn Expansion

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2465		Accepted: 666

Description

Farmer John has N (1 <= N <= 25,000) rectangular barns on his farm, all with sides parallel to the X and Y axes and integer corner coordinates in the range 0..1,000,000. These barns do not overlap although they may share corners and/or sides with other barns.

Since he has extra cows to milk this year, FJ would like to expand some of his barns. A barn has room to expand if it does not share a corner or a wall with any other barn. That is, FJ can expand a barn if all four of its walls can be pushed outward by at least some amount without bumping into another barn. If two barns meet at a corner, neither barn can expand.

Please determine how many barns have room to expand.

Input

Line 1: A single integer, N

Lines 2..N+1: Four space-separated integers A, B, C, and D, describing one barn. The lower-left corner of the barn is at (A,B) and the upper right corner is at (C,D).

Output

Line 1: A single integer that is the number of barns that can be expanded.

Sample Input

Sample Output

Hint

Explanation of the sample:

There are 5 barns. The first barn has its lower-left corner at (0,2) and its upper-right corner at (2,7), and so on.

Only two barns can be expanded --- the first two listed in the input. All other barns are each in contact with at least one other barn.

题意：二维坐标给定N块矩阵，如果其中某块矩阵与其他任意一块矩阵有接触的话(边或者顶点有接触)，那么这块矩阵就无法扩充，问到底有多少矩阵是可以扩充的。

思路：分别用平行于y轴和x轴方向的直线扫描平面。具体做法，现在不妨用平行于y轴的直线来扫描平面，扫描到如下情况时，我们首先给所有顶点编号，不妨从下往上编，这样就得从下往上考虑，如果当前考虑到的顶点是一个矩阵一条边的起始点，那么记录器num++，

遇到的顶点是一条边的终点，num--，表示这条边不会再和接下来的矩阵存在重叠的关系。如果遇到了某个起始点，num++后num的值大于等于2，说明这个顶点左右两边的矩阵一定是有接触的(意味着一条边还没走到终点又碰到了一个起始点，那么这两条边就就有一部分重叠在了一起)，例如图中，先碰到了顶点1，后来又碰到了顶点2，那么之后那部分的边就是左右矩阵所公用的。那么遇到一个终点，num--后num==0,说明这个终点之后的顶点就不能和之前的矩阵有公共边的关系了。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<queue>

#include<set>

#include<vector>

#include<cstring>

#include<string>

#include<cmath>

using namespace std;

const int N_MAX =+ ;

int N;

enum point_type{

    START, END

};

struct P {

    int x, y;

    int id;//坐标点是属于第几个矩形的

    point_type type;

    P(int x,int y,int id,point_type type):x(x),y(y),id(id),type(type) {}

    bool operator <(const P&b)const {

        if (x != b.x)return x < b.x;

        else if (y != b.y)return y < b.y;

        else return type < b.type;

    }

};

//P p1[N_MAX], p2[N_MAX];

vector<P>p1;

vector<P>p2;

bool ok[N_MAX];

void scan( vector<P>p1) {

     vector<P>::iterator it = p1.begin();

     int connect_num = ;

     int cur_x = it->x;

     bool illegal = ;

    while (it!=p1.end()) {

        if (cur_x != it->x) {//扫描到了新的一列上

            connect_num = ;

            cur_x = it->x;

            illegal = ;

        }

        int cur_y = it->y;

        while (it!=p1.end()&&cur_x==it->x&&cur_y==it->y) {//处理同一个坐标点或者同一列上的坐标点

            if (illegal)ok[it->id] = true;//这个点重合了

            if (it->type == START) {

                connect_num++;

                if (connect_num >= )illegal = true;//按y坐标向上扫描扫描到某个顶点开始有边或者点重合了，那么两边的矩阵都不能扩展了

            }

            if (it->type == END) {

                connect_num--;

                if (connect_num == )illegal = false;

            }

            it++;

        }

    }

}

void clear() {

    p1.clear();

    p2.clear();

}

int main() {

    while (scanf("%d",&N)!=EOF) {

        for (int i = ;i<N;i++) {

           int A,B,C,D;

           scanf("%d%d%d%d",&A,&B,&C,&D);

           p1.push_back(P(A, B, i, START));

           p1.push_back(P(C, B, i, START));

           p1.push_back(P(A,D,i,END));

           p1.push_back(P(C, D, i, END));

           p2.push_back(P(B,A,i,START));

           p2.push_back(P(D,A,i,START));

           p2.push_back(P(B,C,i,END));

           p2.push_back(P(D, C, i, END));

        }

        sort(p1.begin(), p1.end());

        sort(p2.begin(),p2.end());

        memset(ok, , sizeof(ok));

        scan(p1);

        scan(p2);

        printf("%d\n", count(ok, ok + N,false));

        clear();

    }

    return ;

}

巴特西

poj 3168 Barn Expansion

最新文章

热门文章