Portal

Solution:

Record the time period of a meteor in the field of vision as (L, R),

In order to make all (L, R) Take all integers , First, zoom in on the coordinates .

The magnification can be taken as

LCM(1, 2, ..., 10)= 2520

Then calculate : from 0 The moment begins , The number of meteors per unit time , It's an array :

a[0], ..., a[M]

Obviously this can be done with the help of Line segment tree , But it's hard to avoid being cumbersome .

Considering the particularity of the interval operation of this problem : Every time I'm in the interval [L, R) Add one to the elements inside , It's more convenient to use differential sequence .

Array a[0...M] The difference sequence of d[0...M] Defined as :

d[0]=a[0],

d[i]=a[i]-a[i-1], i>0

For this question , We just need to maintain the array a[ ] The difference sequence of d[ ] that will do .

------------------------------------------------------------------------------------

Implementation:

Of course, we can discretize it first , But the following implementation uses map (also called "asscociated array") Avoid discretization :

#include <bits/stdc++.h>
using namespace std; const int N=1e5+;
const int INF=0x3f3f3f3f; int x[N], y[N], a[N], b[N], t[N][];
int n, w, h; map<int,int> mp;

//! Repeating
void get_t(int i){
int tx1, tx2, ty1, ty2;
if(a[i]==){
if(x[i]> && x[i]<w){
tx1=;
tx2=INF;
}
else{
tx1=tx2=;
}
}
else{
tx1=-x[i]/a[i];
tx2=(w-x[i])/a[i];
}
if(b[i]==){
if(y[i]> && y[i]<h){
ty1=;
ty2=INF;
}
else{
ty1=ty2=;
}
}
else{
ty1=-y[i]/b[i];
ty2=(h-y[i])/b[i];
}
t[i][]=max(min(tx1, tx2), min(ty1, ty2));
t[i][]=min(max(tx1, tx2), max(ty1, ty2));
t[i][]=max(t[i][], );
if(t[i][]>t[i][]){
mp[t[i][]+]++;
mp[t[i][]]--;
}
} int main(){
int T;
for(cin>>T; T--; mp.clear()){
cin>>w>>h>>n;
w*=;
h*=;
mp[];
for(int i=; i<n; i++){
cin>>x[i]>>y[i]>>a[i]>>b[i];
x[i]*=, y[i]*=;
get_t(i);
}
// As with any other type specifier, we can define mutiple variables using auto.
// Because a declaratin can involve only a single base type, the initializers for all the
// variables in the declaration must have types that are consistent with each other.
int ans =;
// tedious
auto i=mp.begin(), j=i;
++j; for(; j!=mp.end(); ++i, ++j){
j->second+=i->second;
ans=max(ans, j->second);
}
cout << ans <<'\n';
} return ;
}

The code is poorly written :

  • repeat , Do not conform to the Keep DRY (Don't Repeat Yourself) principle
  • All arrays don't need to be opened
  • Calculate the preceding term and (prefix sum) Too complicated , It's stupid (dull)

---------------------------------------------------------------------------------------

In a word, it's too ugly to see any more , Code like this , What's the difference with salted fish .....

Enhanced:

#include <bits/stdc++.h>
using namespace std; const int N=1e5+;
const int INF=0x3f3f3f3f;
int x, y, a, b;
int n, w, h; map<int,int> mp; void get_t(int &L, int &R, int v, int p, int b){
if(v){
L=max(L, min(-p/v, (b-p)/v));
R=min(R, max(-p/v, (b-p)/v));
}
else if(p<= || p>=b) R=L;
} int main(){
ios::sync_with_stdio(false); int T;
for(cin>>T; T--; mp.clear()){
cin>>w>>h>>n;
w*=;
h*=; for(int i=, L, R; i<n; i++){
cin>>x>>y>>a>>b;
x*=, y*=;
L=, R=INF;
get_t(L, R, a, x, w);
get_t(L, R, b, y, h); if(R>L)
mp[L]++, mp[R]--;
}
int ans =, sum=; for(auto i:mp){
sum+=i.second;
ans=max(sum, ans);
}
cout << ans <<'\n';
}
return ;
}

-----------------------------------------------

There is a more wonderful realization :

#include <bits/stdc++.h>
using namespace std; const int N=1e5+;
const int INF=0x3f3f3f3f;
int x, y, a, b;
int n, w, h; vector<pair<int,int>> vec; //Don't repeat yourself. (keep DRY) void get_t(int &L, int &R, int v, int p, int b){
if(v){
L=max(L, min(-p/v, (b-p)/v));
R=min(R, max(-p/v, (b-p)/v));
}
else if(p<= || p>=b) R=L;
} int main(){
ios::sync_with_stdio(false); int T;
for(cin>>T; T--; ){
cin>>w>>h>>n;
w*=;
h*=; vec.clear(); for(int i=, L, R; i<n; i++){
cin>>x>>y>>a>>b;
x*=, y*=;
L=, R=INF;
get_t(L, R, a, x, w);
get_t(L, R, b, y, h);
if(R>L){ //error-prone
vec.push_back({L, });
vec.push_back({R, -});
}
}
sort(vec.begin(), vec.end());
int ans =, sum=; for(auto i:vec){
sum+=i.second;
ans=max(sum, ans);
}
cout << ans <<'\n';
} return ;
}

words cannot express all one intends to say , Let the reader enjoy it .........

UVA 1398 Meteor More articles about

  1. 【 translate 】Meteor Novice tutorial : Add new features to the leaderboard

    original text :http://danneu.com/posts/6-meteor-tutorial-for-fellow-noobs-adding-features-to-the-leaderboard-dem ...

  2. Using View and Data API with Meteor

    By Daniel Du I have been studying Meteor these days, and find that Meteor is really a mind-blowing f ...

  3. POJ 3669 Meteor Shower【BFS】

    POJ 3669 To see the meteor shower , Unexpectedly, the meteor will smash up, down, left and right in the five points . Each meteor falls at a different location and time , I want to live , If you can live , What's the shortest escape time ? Ideas : Sort the meteor shower , Then set the value of each point on the map as the most ...

  4. How to be in Meteor Use in npm modular ?

    First , Please be there. AtmosphereJs Search for related packages on . Try to use existing packages as much as possible , Instead of packaging . There are two ways to use it in a project npm Module . Encapsulated in the Meteor Packages and add packages to the project . Use meteor cr ...

  5. windows Next Meteor+AngularJS The pit of development

    If there's something complicated, I'll post it , Only easy to solve pits are recorded here . 1. windows Next, add smart package. Drop the downloaded package directly to meteor package in . Remember to change the folder name to smart.j ...

  6. Meteor + node-imap(nodejs) + mailparser(nodejs) Complete sending and receiving mail

    Version information : Meteor:windows MIS install  0.6.4 node-imap:npm designated 0.8.0 edition , Not by default 0.7.x edition . mailparser:npm install 0.3.6 Here's a record of what you stepped on ...

  7. Give by hand Meteor increase smart package Methods

    windows It's impossible to install mrt(Meteor Package management tools ). But also good smart package It's just a folder , Don't need to Meteor What to register in . So directly smart package Throw it me ...

  8. Meteor+AngularJS: Super fast Web Development

        For better description Meteor and AngularJS Why is it worth talking about , Let me start with a personal review of the past three years WEB Changes in development :      Three years ago , I've started trying to separate the front and back ends , The back-end using php Lightweight business logic framework for . but ...

  9. uva 1354 Mobile Computing ——yhx

    aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABGcAAANuCAYAAAC7f2QuAAAgAElEQVR4nOy9XUhjWbo3vu72RRgkF5

Random recommendation

  1. Eclipse Common shortcut keys

    Eclipse Common shortcut key 1,       Ctrl+S, Save the document . 2,       Tab, Multiple lines moving right at the same time : To select multiple lines 3,       shlft+tab, Multiple lines moving left at the same time , To select multiple lines 4,       ...

  2. In depth understanding of jQuery Plug-in development ( turn )

    from :http://blog.jobbole.com/30550/ If you read this article , I'm sure you will no doubt think that jQuery It's an easy-to-use library .jQuery Maybe it's easy to use , But there are still some strange things about it ...

  3. Vim Common configuration (~/.vimrc)( Reprint )

    Original address :http://www.2cto.com/os/201309/246271.html " This must be first, beacuse it changes other o ...

  4. ThinkPHP send out post request

    function post($url, $param=array()){ if(!is_array($param)){ throw new Exception(" Parameter must be array&quo ...

  5. [Python Reptile notes ][ Get started with a blog ( One )]

    [Python Reptile notes ][ Get started with a blog ( One )] label ( The blank space to separate ): Python Reptiles 2016 Summer vacation Source blog : Break away from inadequacy and ignorance 1. Simple crawling specific url Of html Code import urllib ...

  6. QTableView Add progress bar Add a button TreeWidget Additions and deletions

    http://www.cnblogs.com/li-peng/p/3961386.html http://www.cnblogs.com/li-peng/p/3961843.html http://w ...

  7. Maven Can't download SNAPSHOT But it can be downloaded RELEASE The package solution

    In use ,Maven The default configuration is not to download SNAPSHOT Bag , This is a conclusion based on the consideration of code stability . introduce SNAPSHOT The biggest problem with Bao is , because SNAPSHOT Allow duplicate Uploads , So reference a package like this ...

  8. really - close win10 Security Center (windows defender)

    Original by geek , Reprint please indicate . Infringement must be investigated First of all Task manager Start item Ban second   Use win+R, Open the run command input :gpedit.msc Then click OK Find... Under the management module Windows Components , Next, open the drop-down menu , find Wi ...

  9. [cookie piece ]cookie-parser And parser.js

    cookie-parser The role of , It's official :Parse Cookie header and populate req.cookies with an object keyed by the coo ...

  10. mac Error downloading module OSError: [Errno 13] Permission denied: &#39;/Library/Python/2.7/site-packages/chardet&#39;

    Original address :https://www.cnblogs.com/liangyan-1989/p/8143129.html installed pip after , Use pip install selenium Report the following mistakes OSError ...