本文主要是介绍poj 2318 TOYS（计算几何：求叉积），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出一个被n条线段分割的矩形
有m次询问，每次找到这个点所属的四边形
用二分的方法，找到对左侧线段叉积为正，右侧线段叉积为负的情况
直接套模板，代码如下：
/* ***********************************************
Author :yinhua
Created Time :2014年12月01日 星期一 19时19分20秒
File Name :poj2318.cpp
************************************************ */#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 5050
using namespace std;struct Point {int x, y;Point() { }Point(int _x, int _y) {x = _x;y = _y;}Point operator -(const Point &b) const {return Point(x-b.x, y-b.y);}int operator *(const Point &b) const {return x*b.x+y*b.y;}int operator ^(const Point &b) const {return x*b.y-y*b.x;}
};struct Line {Point s, e;Line() { }Line(Point _s, Point _e) {s = _s; e = _e;}
};int xmult(Point p0, Point p1, Point p2) {//p0点与线段p1 p2的叉积return (p1-p0)^(p2-p0);
}Line line[MAXN];
int ans[MAXN];int main(void) {int m, n, x1, y1, x2, y2;bool first = true;while(~scanf("%d", &n) && n) {if(first) first = false;else puts("");scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);int ui, li;for(int i=0; i<n; ++i) {scanf("%d%d", &ui, &li);line[i] = Line(Point(ui, y1), Point(li, y2));}line[n] = Line(Point(x2, y1), Point(x2, y2));int x, y;Point p;memset(ans, 0, sizeof(ans));while(m--) {scanf("%d%d", &x, &y);p = Point(x, y);int l = 0, r = n;int tmp;while(l <= r) {int mid = (l+r)>>1;if(xmult(p, line[mid].s, line[mid].e) < 0) {//点在当前线的左侧tmp = mid;r = mid-1;} else l = mid+1;//点在当前线的右侧}ans[tmp]++;}for(int i=0; i<=n; ++i) {printf("%d: %d\n", i, ans[i]);}}return 0;
}这篇关于poj 2318 TOYS（计算几何：求叉积）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
