poj - 2318 - TOYS
题意：将m个玩具扔进一个从左到右分成n个块的箱子中，问每个分块里有多少个玩具（箱子的左上角坐标为(x1, y1)，箱子右下角坐标为(x2, y2)，中间n条分隔栏的上坐标的横坐标为U[i]，下坐标的横坐标为L[i]）。
——>>人生第一道ACM几何题目！翻了一下白书加强版——汝佳的《训练指南》，恰恰有判断点在多边形内的方法——转角法，写上submit，处理不好，得了个TLE，Google一下，看到了“二分”这个字眼，立马回到自己的代码，将原来的两个for寻找点的位置换成二分分块寻找点的位置（用叉积判断点在目前探寻边的左边还是右边），submit，这次得了个PE，回看题目：“Separate the output of different problems by a single blank line.”，难道说最后一组数据也要空行（其实已经可以肯定），再改，125MS——AC！
[cpp] www.zzzyk.com
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 5000 + 10; //0 < n <= 5000, 0 < m <= 5000
const double eps = 1e-10; //为了精度
int cnt[maxn]; //各个分块的玩具数量
struct Point //点数据类型
{
double x, y;
Point(double x = 0, double y = 0):x(x), y(y){}
};
typedef Point Vector; //引用为向量类型
Vector operator - (Vector A, Vector B) //重载-运算符
{
return Vector(A.x-B.x, A.y-B.y);
}
int dcmp(double x) //为了精度
{
if(fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
double Cross(Vector A, Vector B) //叉积函数
{
return A.x*B.y - A.y*B.x;
}
Vector U[maxn], L[maxn]; //输入的上部点与下部点
int main()
{
int n, m, i;
double x1, y1, x2, y2;
while(~scanf("%d", &n))
{
if(!n) return 0;
scanf("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2);
for(i = 1; i <= n; i++) //将箱子的左端存了U[0]与L[0]，故输入的边从1开始
{
scanf("%lf%lf", &U[i].x, &L[i].x);
U[i].y = y1;
L[i].y = y2;
}
U[0].x = x1; U[0].y = y1; //箱子左端
L[0].x = x1; L[0].y = y2;
U[n+1].x = x2; U[n+1].y = y1; //箱子右端
L[n+1].x = x2; L[n+1].y = y2;
memset(cnt, 0, sizeof(cnt)); //初始化
Point p;
for(i = 1; i <= m; i++)
{
scanf("%lf%lf", &p.x, &p.y);
int l = 0, r = n+1; //二分确定位置
while(l < r)
{
int M = l + (r - l) / 2;
if(dcmp(Cross(U[M]-L[M], p-L[M])) > 0) r = M;
else l = M+1;
}
cnt[l-1]++;
}
for(i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]);
printf("\n"); //气！开始理解为最后一组不用空行，PE了一次
}
return 0;
}
补充：软件开发 , C++ ,
