本文主要是介绍POJ 2318 几何 POJ 2398，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出0 , 1 , 2 ... n 个盒子， 和m个点， 统计每个盒子里面的点的个数。
const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
}struct Point{double x , y ;Point(){}Point(double _x , double _y):x(_x),y(_y){}Point operator + (Point o){return Point(add(x , o.x) , add(y , o.y)) ;}Point operator - (Point o){return Point(add(x , -o.x) , add(y , -o.y)) ;}double operator ^(Point o){return add(x*o.y , -y*o.x) ;}void read(){scanf("%lf%lf" ,&x , &y) ;}
};Point up[5008] , down[5008] ;
int cnt[5008] ;
int main(){int i , j , n , m , T = 1 ;Point p ;while(cin>>n && n){scanf("%d" , &m) ;up[0].read() ;down[n+1].read() ;down[0] = Point(up[0].x , down[n+1].y) ;up[n+1] = Point(down[n+1].x , up[0].y) ;for(i = 1 ; i <= n ; i++){scanf("%lf%lf" , &up[i].x , &down[i].x) ;up[i].y = up[0].y ;down[i].y = down[n+1].y ;}memset(cnt , 0 , sizeof(cnt)) ;int L , R , M , c , s ;while(m--){p.read() ;L = 1 , R = n+1 ;while(L <= R){M = (L + R) >> 1 ;c = (up[M] - down[M]) ^ (p - down[M]) ;if(c > 0){s = M - 1 ;R = M - 1 ;}else L = M + 1 ;}cnt[s]++ ;}if(T != 1) puts("") ;T++ ;for(i = 0 ; i <= n ; i++) printf("%d: %d\n" , i , cnt[i]) ;}return 0 ;
}
POJ 2398 边没有排序， 统计不同。
const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
}struct Point{double x , y ;Point(){}Point(double _x , double _y):x(_x),y(_y){}Point operator + (Point o){return Point(add(x , o.x) , add(y , o.y)) ;}Point operator - (Point o){return Point(add(x , -o.x) , add(y , -o.y)) ;}double operator ^(Point o){return add(x*o.y , -y*o.x) ;}void read(){scanf("%lf%lf" ,&x , &y) ;}
};struct Line{Point s , t ;Line(){}Line(Point _s , Point _t):s(_s),t(_t){}int intersect(Line o){return intersection(s , t , o.s , o.t) ;}void read(){s.read() , t.read() ;}friend bool operator < (const Line A ,const Line B){return A.s.x < B.s.x ;}
};Point up[5008] , down[5008] ;
Line line[5008] ;
int cnt[5008] ;
map<int , int> mp ;
map<int , int> ::iterator it ;int main(){int i , j , n , m , T = 1 ;Point p ;while(cin>>n && n){scanf("%d" , &m) ;up[0].read() ;down[n+1].read() ;down[0] = Point(up[0].x , down[n+1].y) ;up[n+1] = Point(down[n+1].x , up[0].y) ;for(i = 1 ; i <= n ; i++){scanf("%lf%lf" , &up[i].x , &down[i].x) ;up[i].y = up[0].y ;down[i].y = down[n+1].y ;}for(i = 0 ; i <= n+1 ; i++)line[i] = Line(up[i] , down[i]) ;sort(line , line+2+n) ;mp.clear() ;memset(cnt , 0 , sizeof(cnt)) ;int L , R , M , c , s ;while(m--){p.read() ;L = 1 , R = n+1 ;while(L <= R){M = (L + R) >> 1 ;c = (line[M].s - line[M].t) ^ (p - line[M].t) ;if(c > 0){s = M - 1 ;R = M - 1 ;}else L = M + 1 ;}cnt[s]++ ;}for(i = 0 ; i <= n ; i++){if(cnt[i]) mp[cnt[i]]++ ;}puts("Box") ;for(it = mp.begin() ; it != mp.end() ; it++){printf("%d: %d\n" , it->first , it->second) ;}}return 0 ;
}
这篇关于POJ 2318 几何 POJ 2398的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
