873      技術社區[雲棲]

uva 1398 - Meteor 模擬 99

   最近多練練簡單題，簡單的掃描線

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int w,h,n;
const int inf=1e9;
struct point
{
    point(){};
    point(int x,int y):time(x),type(y){};
    int time;
    int type; //1為開始，-1為結束
    bool operator <(const point &a) const
    {
        return time<a.time||(a.time==time&&type<a.type);
    }
};
point org[200005];
int update(int w,int b,int a,int &L,int &R)
{
    if(a==0)
    {
        if(b<=0||b>=w)R=L-1;
    }
    else if(a>0)
    {
        L=max(L,-2520*b/a);
        R=min(R,2520*(w-b)/a);
    }
    else
    {
        L=max(L,2520*(w-b)/a);
        R=min(R,-2520*b/a);
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int cnt=0;
        scanf("%d%d%d",&w,&h,&n);
        int x,y,vx,vy;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x,&y,&vx,&vy);
            int l=0,r=inf;
            update(w,x,vx,l,r);
            update(h,y,vy,l,r);
            if(l<r)
            {
                org[cnt++]=point(l,1);
                org[cnt++]=point(r,-1);
            }
        }
        sort(org,org+cnt);
        int ans=0,t=0;
        for(int i=0;i<cnt;i++)
        {
            t+=org[i].type;
            ans=max(ans,t);
        }
        printf("%d\n",ans);
    }
}

最後更新：2017-04-03 15:22:11

  上一篇： 網絡子係統22_隊列規則傳輸接口

  下一篇： COM編程入門第一部分——什麼是COM，如何使用COM