扫描线 – hahaschool

题意

请参考LRJ白书第一章例题20

思路

扫描线。

这个题分为两部分，首先是要求出每一颗流星划过取景框的时间区间，这一步反而是这个题最复杂的地方，因为要讨论许多种情况，具体的讨论策略可以参考下面的代码。

求出来所有的区间之后，问题转化为选出一条线，使得这条线穿过的区间最多，这里就是扫描线算法派上用场的时候了。其实实现很简单，就是对于每个区间的两个端点，分别创建一个表示起始的事件和一个表示结束的事件，然后把所有事件按照出现的时间排序，接下来从小往大检查，遇到开始事件的时候计数器+1，遇到结束事件的时候计数器-1.

这里有一个问题，如果开始事件和结束事件恰好位于同一时点，怎么办？注意到我们的区间都是开的，这样我们只要优先处理结束事件，就不会导致解偏大了（这里面的逻辑需要自己试着理解一下）。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>
#include <cassert>

using namespace std;

int w,h;
int n;

struct Event {
    int t;
    int dir;
    bool operator < (const Event &b) const {
        if(t == b.t) {
            return dir < b.dir;
        }
        return t < b.t;
    }
};

vector<Event> event;

int main() {
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++) {
        scanf(" %d %d %d",&w,&h,&n);
        event.clear();
        for(int i = 1; i <= n; i++) {
            double x,y,a,b;
            scanf(" %lf %lf %lf %lf",&x,&y,&a,&b);
            bool fail = false;
            int l = 0,r = 0x3f3f3f3f;
            if(a != 0) {
                //Left Side
                int tls = -(x*2520/a);
                //Right Side
                int trs = (w-x)*2520/a;
                if(a > 0){
                    l = max(l,tls);
                    r = min(r,trs);
                }else{
                    l = max(l,trs);
                    r = min(r,tls);
                }
            }else{
                if(x <= 0 || x >= w){
                    fail = true;
                }
            }
            if(b != 0) {
                //Upper Side
                int tus = (h-y)*2520/b;
                //Down Side
                int tds = -(y*2520/b);
                if(b > 0){
                    l = max(l,tds);
                    r = min(r,tus);
                }else{
                    l = max(l,tus);
                    r = min(r,tds);
                }
            }else{
                if(y <= 0 || y >= h){
                    fail = true;
                }
            }
            Event tmp;
            if(!fail && l < r){
                tmp.t = l;
                tmp.dir = 1;
                event.push_back(tmp);
                tmp.t = r;
                tmp.dir = -1;
                event.push_back(tmp);
            }
        }
        sort(event.begin(),event.end());
        int cur = 0;
        int res = 0;
        for(int i = 0; i < event.size(); i++) {
            cur += event[i].dir;
            res = max(res,cur);
        }
        printf("%d\n",res);
    }

    return 0;
}

100

101

102

103

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

#include <cassert>

using namespace std;

int w,h;

int n;

struct Event {

int t;

int dir;

bool operator < (const Event &b) const {

if(t == b.t) {

return dir < b.dir;

}

return t < b.t;

}

};

vector<Event> event;

int main() {

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++) {

scanf(" %d %d %d",&w,&h,&n);

event.clear();

for(int i = 1; i <= n; i++) {

double x,y,a,b;

scanf(" %lf %lf %lf %lf",&x,&y,&a,&b);

bool fail = false;

int l = 0,r = 0x3f3f3f3f;

if(a != 0) {

//Left Side

int tls = -(x*2520/a);

//Right Side

int trs = (w-x)*2520/a;

if(a > 0){

l = max(l,tls);

r = min(r,trs);

}else{

l = max(l,trs);

r = min(r,tls);

}

}else{

if(x <= 0 || x >= w){

fail = true;

}

if(b != 0) {

//Upper Side

int tus = (h-y)*2520/b;

//Down Side

int tds = -(y*2520/b);

if(b > 0){

l = max(l,tds);

r = min(r,tus);

}else{

l = max(l,tus);

r = min(r,tds);

}

}else{

if(y <= 0 || y >= h){

fail = true;

}

Event tmp;

if(!fail && l < r){

tmp.t = l;

tmp.dir = 1;

event.push_back(tmp);

tmp.t = r;

tmp.dir = -1;

event.push_back(tmp);

}

sort(event.begin(),event.end());

int cur = 0;

int res = 0;

for(int i = 0; i < event.size(); i++) {

cur += event[i].dir;

res = max(res,cur);

}

printf("%d\n",res);

}

return 0;

}

Tag: 扫描线

LA3905 Meteor

题意

思路

代码