博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
3905 - Meteor
阅读量:5840 次
发布时间:2019-06-18

本文共 5178 字,大约阅读时间需要 17 分钟。

The famous Korean internet company nhn has provided an internet-based photo service which allows The famous Korean internet company users to directly take a photo of an astronomical phenomenon in space by controlling a high-performance telescope owned by nhn. A few days later, a meteoric shower, known as the biggest one in this century, is expected. nhn has announced a photo competition which awards the user who takes a photo containing as many meteors as possible by using the photo service. For this competition, nhn provides the information on the trajectories of the meteors at their web page in advance. The best way to win is to compute the moment (the time) at which the telescope can catch the maximum number of meteors.

You have n <tex2html_verbatim_mark>meteors, each moving in uniform linear motion; the meteor mi <tex2html_verbatim_mark>moves along the trajectory pi + t×vi <tex2html_verbatim_mark>over time t <tex2html_verbatim_mark>, where t <tex2html_verbatim_mark>is a non-negative real value, pi <tex2html_verbatim_mark>is the starting point of mi <tex2html_verbatim_mark>and vi <tex2html_verbatim_mark>is the velocity of mi <tex2html_verbatim_mark>. The point pi = (xi, yi) <tex2html_verbatim_mark>is represented by X <tex2html_verbatim_mark>-coordinate xi <tex2html_verbatim_mark>and Y <tex2html_verbatim_mark>-coordinate yi <tex2html_verbatim_mark>in the (X, Y) <tex2html_verbatim_mark>-plane, and the velocity vi = (ai, bi) <tex2html_verbatim_mark>is a non-zero vector with two components ai <tex2html_verbatim_mark>and bi <tex2html_verbatim_mark>in the (X, Y) <tex2html_verbatim_mark>-plane. For example, if pi = (1, 3) <tex2html_verbatim_mark>and vi = (-2, 5) <tex2html_verbatim_mark>, then the meteor mi <tex2html_verbatim_mark>will be at the position (0, 5.5) at time t = 0.5 <tex2html_verbatim_mark>because pi + t×vi = (1, 3) + 0.5×(-2, 5) = (0, 5.5) <tex2html_verbatim_mark>. The telescope has a rectangular frame with the lower-left corner (0, 0) and the upper-right corner (w, h) <tex2html_verbatim_mark>. Refer to Figure 1. A meteor is said to be in the telescope frame if the meteor is in the interior of the frame (not on the boundary of the frame). For exam! ple, in Figure 1, p2, p3, p4 <tex2html_verbatim_mark>, and p5 <tex2html_verbatim_mark>cannot be taken by the telescope at any time because they do not pass the interior of the frame at all. You need to compute a time at which the number of meteors in the frame of the telescope is maximized, and then output the maximum number of meteors.

 

\epsfbox{p3905.eps} <tex2html_verbatim_mark>

 

Input 

Your program is to read the input from standard input. The input consists of T <tex2html_verbatim_mark>test cases. The number of test cases T <tex2html_verbatim_mark>is given in the first line of the input. Each test case starts with a line containing two integers w <tex2html_verbatim_mark>and h <tex2html_verbatim_mark>(1$ \le$w, h$ \le$100, 000) <tex2html_verbatim_mark>, the width and height of the telescope frame, which are separated by single space. The second line contains an integer n <tex2html_verbatim_mark>, the number of input points (meteors), 1$ \le$n$ \le$100, 000 <tex2html_verbatim_mark>. Each of the next n <tex2html_verbatim_mark>lines contain four integers xi, yi, ai <tex2html_verbatim_mark>, and bi <tex2html_verbatim_mark>; (xi, yi) <tex2html_verbatim_mark>is the starting point pi <tex2html_verbatim_mark>and (ai, bi) <tex2html_verbatim_mark>is the nonzero velocity vector vi <tex2html_verbatim_mark>of the i <tex2html_verbatim_mark>-th meteor; xi <tex2html_verbatim_mark>and yi <tex2html_verbatim_mark>are integer values between -200,000 and 200,000, and ai <tex2html_verbatim_mark>and bi <tex2html_verbatim_mark>are integer values between -10 and 10. Note that at least one of ai <tex2html_verbatim_mark>and bi <tex2html_verbatim_mark>is not zero. These four values are separated by single spaces. We assume that all starting points pi <tex2html_verbatim_mark>are distinct.

 

Output 

Your program is to write to standard output. Print the maximum number of meteors which can be in the telescope frame at some moment.

 

Sample Input 

 

2 4 2 2 -1 1 1 -1 5 2 -1 -1 13 6 7 3 -2 1 3 6 9 -2 -1 8 0 -1 -1 7 6 10 0 11 -2 2 1 -2 4 6 -1 3 2 -5 -1

 

Sample Output 

 

1 2
#include"iostream"#include"algorithm"#include"cstdio"using namespace std;void updata(int x,int a,int w,int &L,int &R){    if(a==0)    {        if(x<=0||x>=w)          R=L-1;    }    else if(a>0)   //x+at=0  x+at=w;    {        L=max(L,-x*(2520/a));        R=min(R,(w-x)*(2520/a));    }    else    {        L=max(L,(w-x)*(2520/a));        R=min(R,-x*(2520/a));    }}const int maxn=100000+10;struct Event{    int x;    int type;    bool operator <(const Event &a) const    {        return x
a.type); }}events[maxn*2];int main(){ int t; scanf("%d",&t); while(t--) { int w,h,n,e=0; scanf("%d%d%d",&w,&h,&n); for(int i=0;i
L) { events[e++]=(Event){L,0}; events[e++]=(Event){R,1}; } } sort(events,events+e); int cnt=0,ans=0; for(int i=0;i
View Code

 

转载于:https://www.cnblogs.com/767355675hutaishi/p/3804256.html

你可能感兴趣的文章
抽象类的调用
查看>>
使用硬盘,安装双系统,Win7+CentOS
查看>>
Javascript学习总结
查看>>
php 用正则替换中文字符一系列问题解决
查看>>
ActiveMQ应用笔记一:基本概念&安装
查看>>
大话数据结构之四(串)
查看>>
加热炉简是新来的整个系统的板
查看>>
Mockito使用注意事项
查看>>
[LeetCode] Palindrome Linked List 回文链表
查看>>
UVA - 825Walking on the Safe Side(dp)
查看>>
android大概是通过logcat拦截Log
查看>>
关于codeMirror插件使用的一个坑
查看>>
评论:人才流失强力折射出现实畸形人才观
查看>>
git服务器gitlab之搭建和使用--灰常好的git服务器【转】
查看>>
基于机器学习的web异常检测——基于HMM的状态序列建模,将原始数据转化为状态机表示,然后求解概率判断异常与否...
查看>>
分享一种需求评审的方案
查看>>
虚拟运营商10月或大面积放号 哭穷背后仍有赢家
查看>>
Server2016开发环境配置
查看>>
分布式光伏发电建设中的逆变器及其选型
查看>>
增强网络安全防御 推动物联网走向应用
查看>>