POJ2318【判断点在直线哪一侧+二分查找区间】
2024-08-26 02:04:05
题目大意:给定一个矩形和一些线段,线段将矩形分割为从左至右的若干部分,之后给出一些玩具的坐标,求每个部分中玩具的数量
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct point {
int x, y;
};
struct Node {
point a, b;
}A[5010];
int pos[5010];
bool is_right(int xx, int yy, int mid) {
int ans = (A[mid].a.x - xx)*(A[mid].b.y - yy) - (A[mid].a.y - yy)*(A[mid].b.x - xx);
if (ans < 0)return false;
return true;
}
void search(int xx, int yy, int n) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (is_right(xx, yy, mid)) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
pos[left]++;
}
int main() {
int n, m, i, j, x1, x2, y1, y2;
while (scanf("%d", &n), n) {
scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
for (i = 0; i < n; ++i) {
int xd, xu;
scanf("%d%d", &xu, &xd);
A[i].a.x = xu;
A[i].a.y = y1;
A[i].b.x = xd;
A[i].b.y = y2;
}
memset(pos, 0, sizeof(pos));
for (i = 0; i < m; ++i) {
int xx, yy;
scanf("%d%d", &xx, &yy);
search(xx, yy, n);
}
for (i = 0; i <= n; ++i) {
printf("%d: %d\n", i, pos[i]);
}
printf("\n");
}
return 0;
}
最新文章
- [Erlang 0106] Erlang实现Apple Push Notifications消息推送
- js判断函数是否存在、判断是否为函数
- 类的继承和多态性-编写Java应用程序,定义Animal类,此类中有动物的属性:名称 name,腿的数量legs,统计动物的数量 count;方法:设置动物腿数量的方法 void setLegs(),获得腿数量的方法 getLegs(),设置动物名称的方法 setKind(),获得动物名称的方法 getKind(),获得动物数量的方法 getCount()。定义Fish类,是Animal类的子类,
- 一步一步教你如何解锁被盗的iPhone 6S
- 自定义Drawable
- android开发 自定义图文混排控件
- Python面试必须要看的15个问题
- linux修改系统时间date命令加clock -w
- JavaScript函数使用和DOM节点
- JAVA 调用 R 语言之升华篇
- python基础-函数(9)
- 总结JAVA----IO流中的字节流
- Websocket实现即时通讯
- xml实体注入学习
- Shell-8--数值运算及处理
- 牛客练习赛16 E - 求值
- SDOI2013 R1 Day2
- [Web 前端] inline-block元素设置overflow:hidden属性导致相邻行内元素向下偏移
- 一个分布式 MySQL Binlog 存储系统的架构设计
- python多进程并发