foj 2144 三位几何+区间覆盖
2024-09-21 09:31:15
题目大意:一个人站在三维坐标系下的原点处用炮打蚊子,给出n个蚊子的起始坐标跟单位时间匀速移动的方向向量,距离他R以内的蚊子都可以打到,不过他也需要休息,没蚊子的时候也可以休息下。求他要起来多少次打蚊子。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = ;
const double eps = 1e-;
const double Pi=acos(-1.0); int n, cnt;
double R; inline bool scan_d(double &ret)
{ //如果数据比较多,而输入的数值比较小就不用scanf而用这种输入方法,用scanf会超时
char c; int sgn;
if(c = getchar(),c == EOF) return ; //EOF
while(c != '-' && (c < '' || c > '')) c = getchar();
sgn = (c == '-') ? - : ;
ret = (c == '-') ? : (c - '');
while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');
ret *= sgn;
return ;
} struct Point3
{
double x, y, z;
Point3(double x=,double y=,double z=):x(x),y(y),z(z){}
void get() { scan_d(x); scan_d(y); scan_d(z); }
}; struct Node
{
double x, y;
}f[N]; double Dot(Point3 a,Point3 b){return a.x*b.x+a.y*b.y+a.z*b.z;} inline double min(double a,double b){ return a-b>eps?b:a;}
inline double max(double a,double b){ return a-b>eps?a:b;} void Deal(Point3 p, Point3 q)
{
double a=Dot(q,q);
double b=*Dot(p,q);
double c =Dot(p,p)-R*R;
double t =b*b-*a*c;
if (t < eps) return;
else if (fabs(t) < eps)
{
double i = -b / (2.0 * a);
if (i < ) return;
f[cnt].x = f[cnt].y = i;
}
else
{
double i = (-b + sqrt(t) ) / ( * a);
double j = (-b - sqrt(t) ) / ( * a);
if (i < -eps && j < -eps) return;
else if (i < -eps) i = ;
else if (j < -eps) j = ;
f[cnt].x = min(i, j);
f[cnt].y = max(i, j);
}
cnt++;
} void Init()
{
cnt = ;
Point3 p, v;
scanf("%d%lf", &n, &R);
for (int i = ; i < n; i++)
{
p.get();v.get();
Deal(p, v);
}
} bool mycomp(const Node &a, const Node &b)
{
if (fabs(a.y - b.y) > eps) return a.y - b.y < eps;
return a.x - b.x < eps;
} int Solve()
{
int i,ans = ;
double start = -;
for (i = ; i < cnt; i++)
{
if (f[i].x - start > eps)
{
start = f[i].y;
ans++;
}
}
return ans;
} int main ()
{
int i,Icas;
scanf("%d", &Icas);
for (i = ; i <= Icas; i++)
{
Init();
sort(f, f + cnt, mycomp);
printf("Case %d: %d %d\n", i, cnt, Solve());
}
return ;
}
最新文章
- Hive索引功能测试
- iOS图表库Charts集成与使用
- 使用phpMyAdmin修改MySQL数据库root用户密码
- BaiduTemplate模板引擎使用示例附源码
- Android 创建自己的Camera App
- vi和vim区别及命令详解
- GCD 深入理解:第二部分
- 导出你的GAC Assembly中的DLLS
- AJAX 表单提交 文件上传
- 在Windows cmd中计算行数
- SQL遇到的问题
- Linux学习历程——Centos 7 chown命令
- hadoop 安装之 hadoop、hive环境配置
- vue项目总结
- MTK之DrvGen的使用
- AngularJs_自定义注入对象_笔记1
- 安装及配置sublime
- winform窗体 小程序【移动窗体和阴影】
- sum统计某字段满足某种条件的记录数
- Kubernetes学习之路(九)之kubernetes命令式快速创建应用
热门文章
- PAT (Basic Level) Practise (中文)- 1012. 数字分类 (20)
- MFC中获得各种指针概述(个人觉得是很重要的重点)
- cocos2dx 3.x for lua ";异步加载";实现过程
- 直接用bcdedit创建bootmgr数据库和修复启动菜单
- XML 转 fastJSON
- H5bulider中的微信支付配置注意事项
- sql执行过长,如何入手优化
- Http协议——基本概念
- LayaAir环境TypeScript
- Python虚拟机函数机制之扩展位置参数和扩展键参数(六)