本文主要是介绍POJ 2318 TOYS 二分+叉积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
入门计算几何
判断在哪个区域内只需看跟某条线的叉积即可
可以保证单调性，所以可以进行二分
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 100001
#define MAXM 211111
#define eps 1e-8
#define INF 500000001
using namespace std;
int dblcmp(double d)
{if(fabs(d) < eps) return 0;return d > eps ? 1 : -1;
}
struct point
{double x, y;point(){}point(double _x, double _y):x(_x), y(_y) {};void input(){scanf("%lf%lf", &x, &y);}void output(){printf("%.2f %.2f\n", x, y);}double det(point p){return x * p.y - y * p.x;}point sub(point p){return point(x - p.x, y - p.y);}
}up[5555], down[5555];
double getcross(point a, point o, point b)
{a = a.sub(o);b = b.sub(o);return a.det(b);
}
int num[5555];
int n, m;
int main()
{double xa, xb, ya, yb, ui, li;int cas = 0;while(scanf("%d", &n) != EOF && n){scanf("%d%lf%lf%lf%lf", &m, &xa, &ya, &xb, &yb);if(cas++) puts("");up[0] = point(xa, ya);down[0] = point(xa, yb);for(int i = 1; i <= n; i++){scanf("%lf%lf", &ui, &li);up[i] = point(ui, ya);down[i] = point(li, yb);}up[n + 1] = point(xb, ya);down[n + 1] = point(xb, yb);memset(num, 0, sizeof(num));point tmp;for(int i = 0; i < m; i++){tmp.input();int low = 0, high = n + 1;while(low <= high){int mid = (low + high) >> 1;if(dblcmp(getcross(up[mid], tmp, down[mid])) > 0)low = mid + 1;else high = mid - 1;}num[low - 1] ++;}for(int i = 0; i <= n; i++) printf("%d: %d\n", i, num[i]);}return 0;
}这篇关于POJ 2318 TOYS 二分+叉积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
