최대 교차 하지 않 는 부분 집합 POJ 1328

먼저 최대 교차 하지 않 는 부분 집합 에 대해 설명 하 겠 습 니 다. 많은 집합 [Ai, bi] 이 설치 되 어 있 습 니 다.최대 교차 하지 않 는 부분 집합: 모든 집합 이 교차 하고 발생 하 는 부분 집합, 이런 발생 하 는 부분 집중 의 임 의 두 부분 집합 이 모두 공 집합 이 므 로 발생 하 는 부분 집합 이 반드시 가장 클 것 이다.
알고리즘 프레임 워 크:

for (int i ;i < n ;i++) {
   if (  i    >   j    (i > j) ) {
    		           ；
    		 j  i;
       }
 }
            ；

예제: POJ 1328 문제 의 대의 와 기본: 해안선 을 설치 하 는 것 은 무한 한 직선 이 고 한 쪽 은 육지 이 며 한 쪽 은 바다 이 며 바다 에 작은 섬 이 있 습 니 다. 모든 작은 섬 은 하나의 점 으로 볼 수 있 습 니 다. 해안선 에 레이 더 를 설치 해 야 합 니 다. 모든 레이 더 는 반경 이 d 인 원형 구역 만 덮 을 수 있 습 니 다.바다의 어떤 작은 섬 은 레이더 에 의 해 덮 일 수 있 으 며, 그것 과 어떤 레이더 사이 의 거리 가 d 보다 작 거나 같 을 때 만 덮 일 수 있다.해안선 을 x 축 으로 정의 하고 바 다 는 x 축 상부 에 있 으 며 육 지 는 x 축 하부 에 있 으 며 해양 에서 각 작은 섬의 좌표 위치 (x, y) 와 레이더 가 반경 d 를 덮 고 모든 작은 섬 을 덮 으 려 면 적어도 몇 개의 레이 더 를 설치 해 야 합 니까?입력 은 여러 그룹의 테스트 데 이 터 를 포함 합 니 다.각 조 의 테스트 데이터 의 첫 줄 은 두 개의 정수 n (1 < = n < = 1000) 과 d 를 포함 하여 각각 바다의 작은 섬 수량 과 각 레이더 의 신호 커버 반지름 을 나타 낸다.다음 n 줄 은 한 줄 에 두 개의 정 수 를 포함 하고 모든 작은 섬의 좌 표를 나타 낸다.각 그룹의 테스트 데이터 사이 에 빈 줄 간격 으로n = d = 0 일 때 입력 이 끝 났 음 을 표시 합 니 다.출력 은 각 조 의 테스트 데이터 에 한 줄 을 출력 하고 각 조 의 테스트 데이터 번 호 를 포함 하 며 해당 하 는 최소 몇 개의 레이 더 를 설치 해 야 합 니까?레이 더 를 아무리 설치 해도 신 호 는 모든 작은 섬 을 덮 을 수 없다. 출력 - 1.사고방식: 단순 욕심.각 작은 섬 을 원심 으로 반경 d 의 원 을 만 들 고 X 축 과 교차 하 는 구간 을 찾 아 이 구간 의 어느 한 점 이라도 원심 으로 할 수 있다 는 뜻 으로 이 작은 섬 을 포함한다.이 럴 때 는 모든 작은 섬 을 X 축 구간 에서 찾 아야 한다.교 집합 된 부분 설명 은 원 으로 덮어 쓸 수 있다.이것 은 가장 작은 원 을 계산 하여 먼저 정렬 하고 정렬 한 후에 가장 왼쪽 작은 섬의 오른쪽 구간 을 찾 은 다음 에 모든 작은 섬의 왼쪽 구간 이 오른쪽 구간 보다 작 은 지, 작 으 면 교 집합 이 있다 는 것 을 설명 하고 하나의 원 으로 덮 을 수 있다.이렇게 해서 문 제 를 최대 교차 하지 않 는 구간 집합 문제 로 바 꾸 었 다.

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//   ，left:  x      right：  x    
//       ，      
struct Node{
	double left, right;
	bool operator < (const Node& t1)const {
		return this->right < t1.right;
	}
};

//   
int main() {
	//t:   
	//n:    
	//d:      
	//nums:     
	int t = 0,n,d,nums;

	//  （x,y）   
	int x[1000], y[1000];
	//     
	Node out[1000];
	//   ，  true:   ； false：   ，  “-1”;
	bool fl = true;

	//  。
	//  n，d; “0 0”     
	while (cin >> n >> d && n) {
		//   
		nums = 0;
		fl = true;

		//    （x,y）   
		for (int i = 0; i < n; i++) {
			cin >> x[i] >> y[i];
		}

		//         x      “ x = ((-b) +or-   （b * b - 4 * a * c)) / 2"
		for (int i = 0; i < n; i++) {
			double a, b, c;
			a = 1;
			b = - 2 * x[i];
			c = x[i] * x[i] + y[i] * y[i] - d * d;

			if (b * b - 4 * a * c < 0 || d < 0 || y < 0) {
				fl = false;
				continue;
			}
			out[i].left = (-b - sqrt(b * b - 4 * a * c)) / 2 * a;
			out[i].right = (-b + sqrt(b * b - 4 * a * c)) / 2 * a;

			if (out[i].left > out[i].right) {
				swap(out[i].left, out[i].right);
			}
		}
		//for (int i = 0; i < n; i++) {
		//	cout << out[i].left << "  " << out[i].right << endl;
		//}
		if (!fl) {
			printf("Case %d: %d
", ++t, -1);
			continue;
		}

		//  
		sort(out, out + n);
		int j = 0;

		//          ，      
		for (int i = 1; i < n; i++) {
			if (out[i].left > out[j].right) {
				++nums;
				j = i;
			}
		}
		printf("Case %d: %d
", ++t, nums + 1);
	}
}

최대 교차 하지 않 는 부분 집합:

//          ，      
	for (int i = 1; i < n; i++) {
		if (out[i].left > out[j].right) {
			++nums;
			j = i;
		}
	}