首页 > ACM题库 > HDU-杭电 > HDU 1866 A + B forever!-计算几何-[解题报告] C++
2013
12-23

HDU 1866 A + B forever!-计算几何-[解题报告] C++

A + B forever!

问题描述 :

As always, A + B is the necessary problem of this warming-up contest. But the patterns and contents are different from the previous ones. Now I come up with a new “A + B” problem for you, the top coders of HDU.
As we say, the addition defined between two rectangles is the sum of their area . And you just have to tell me the ultimate area if there are a few rectangles.
Isn’t it a piece of cake for you? Come on! Capture the bright “accepted” for yourself.

输入:

There come a lot of cases. In each case, there is only a string in one line. There are four integers, such as “(x1,y1,x2,y2)”, describing the coordinates of the rectangle, with two brackets distinguishing other rectangle(s) from the string. There lies a plus symbol between every two rectangles. Blanks separating the integers and the interpunctions are added into the strings arbitrarily. The length of the string doesn’t exceed 500.
0<=x1,x2<=1000,0<=y1,y2<=1000.

输出:

For each case, you just need to print the area for this “A+B” problem. The results will not exceed the limit of the 32-signed integer.

样例输入:

(1,1,2,2)+(3,3,4,4)
(1,1,3,3)+(2,2,4,4)+(5,5,6,6)

样例输出:

2
8

第一次做矩形面积的并,这题中借鉴别人的做法,使用标记法求面积的并。

/*
	Author: ACb0y
	Date: 2010-9-02
	Type: geometry (sum area of rectangle)
	ProblemId: hdu 1866
	Result: AC
*/
#include <iostream>
using namespace std;

int max(int a, int b)
{
	return a > b ? a : b;
}

int min(int a, int b)
{
	return a > b ? b : a;
}

int d[4];
int min_x, min_y, max_x, max_y;
char str[510];
int vis[1100][1100];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("1866.txt", "r", stdin);
#endif
	int i, j, k;
	while (gets(str))
	{
		int c = 0;
		int cnt = 0;
		int len = strlen(str);
		memset(vis, 0, sizeof(vis));
		for (i = 0; i < len; i++) 
		{
			if (isdigit(str[i])) 
			{
				int temp = 0;
				while (isdigit(str[i++]))
				{
					temp *= 10;
					temp += str[i - 1] - '0';
				}
				d[c++] = temp;
				i--;
			}
			if (c == 4) 
			{
				c = 0;
				min_x = min(d[0], d[2]);
				max_x = max(d[0], d[2]);
				min_y = min(d[1], d[3]);
				max_y = max(d[1], d[3]);
				for (j = min_x; j < max_x; j++) 
				{
					for (k = min_y; k < max_y; k++) 
					{
						if (!vis[j][k])
						{
							vis[j][k] = 1;
							cnt++;
						}
					}
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/acb0y/article/details/5858264


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c