2278.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2278 on 2006-06-13 at 20:46:58 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
const int ZN = 1 << 20;

uint parse(char*);

class Zone {
public:
	uint b, e;
	bool make();
	bool contain(uint k) const { return b <= k && e >= k; }
	bool operator <(const Zone& z) const { return b < z.b;  }
};
bool Zone::make() {
	char bs[32], es[32];
	scanf("%s", bs);
	if(bs[0] == '#') return false;
	scanf("%s", es);
	b = parse(bs); e = parse(es);
	if(b > e) swap(b, e);
	return true;
}

Zone zone[ZN];

bool find(int, int, uint);

int main()
{
	int i, n, dn = 0;
	char str[32];

	for(n = 0; zone[n].make(); n++) ;
	sort(zone, zone+n);
	uint l = zone[0].b, r = zone[0].e;
	for(i = 1; i < n; i++) {
		if(zone[i].b <= r) { r = max(zone[i].e, r); continue; }
		zone[dn].b = l; zone[dn].e = r; dn++;
		l = zone[i].b; r = zone[i].e;
	}
	zone[dn].b = l; zone[dn].e = r; dn++;
	while(scanf("%s", str) != EOF)
		printf("%s\n", find(0, dn-1, parse(str)) ? "yes" : "no");

	return 0;
}

uint parse(char* str)
{
	int a, b, c, d; sscanf(str, "%d.%d.%d.%d", &a, &b, &c, &d);
	return (a<<24)|(b<<16)|(c<<8)|d;
}
bool find(int b, int e, uint k)
{
	int mid = (b + e) / 2;
	if(zone[mid].contain(k)) return true;
	else if(b == e) return false;
	else if(zone[mid].e < k) return find(mid+1, e, k);
	else return find(b, mid, k);
}