poj 1151(离散化+矩形面积并)
题目链接：http://poj.org/problem?id=1151关于离散化,这篇博客讲的很好：http://www.cppblog.com/MiYu/archive/2010/10/15/129999.aspx
我线段树还是不会写这个。。
借个图：
///离散化
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
const int N = 220;
const double eps = 1e-10;
struct Rec{
double x1,y1;
double x2,y2;
}rec;
double x,y;
int vis;
int n,k;
int cmp(double a,double b){
if(a<b) return 1;
return 0;
}
void input(){
k = 0;
for(int i=0;i<n;i++){
scanf("%lf%lf%lf%lf",&rec.x1,&rec.y1,&rec.x2,&rec.y2);
x = rec.x1,y = rec.y1;
x = rec.x2,y = rec.y2;
}
sort(x,x+k,cmp);
sort(y,y+k,cmp);
}
int binary1(double value){
int mid,l=0,r=k-1;
while(l<r){
mid = (l+r)>>1;
if(fabs(x-value)<eps) return mid;
if(x<value) l = mid+1;
else r = mid-1;
}
return l;
}
int binary2(double value){
int mid,l=0,r=k-1;
while(l<r){
mid = (l+r)>>1;
if(fabs(y-value)<eps) return mid;
if(y<value) l = mid+1;
else r = mid-1;
}
return l;
}
double solve(){
int t1,t2,t3,t4;
for(int i=0;i<n;i++){
t1 = binary1(rec.x1);
t2 = binary1(rec.x2);
t3 = binary2(rec.y1);
t4 = binary2(rec.y2);
for(int j=t1;j<t2;j++){
for(int l = t3;l<t4;l++){
vis=1;
}
}
}
double area = 0;
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
area+=vis*(x-x)*(y-y);
}
}
return area;
}
int main()
{
int cnt=1;
while(scanf("%d",&n)!=EOF&&n){
memset(vis,0,sizeof(vis));
input();
printf("Test case #%d\nTotal explored area: %.2lf\n\n",cnt++,solve());
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15309663/3155102
页:
[1]