prow2012-A3-0011

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意是求，在平面上每次对若干个矩形区域依次进行染色和插除操作，然后给出一条折线段，求这个折线段在染色区域内的长度。 

出这题的初衷是考察直线点向式的应用，一条直线可以用(x0,y0) + k*(X,Y)表示，其中k就是向量增量的倍数。

k一开始是一个[0,1]的区间，随着限制矩形的增加，区间可以覆盖、延长、擦除，

现在的问题就是，得到每个矩形的区间后，如何区间并和区间擦除。

我用的是扫描线的方法，对于每一段，询问当前最大标号的区间是染色还是擦除，以决定这段是否能计入答案。

代码比较清晰，推荐不会做这题的同学们阅读这篇代码学习。



{{{


#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
map<double,int> mat;
double calcK(double x0,double X,double x1){
    if (X==0) return 0;
    return (x1-x0)/X;
}
double Unoin(double &L,double &R,double l,double r){
    if (l>r) swap(l,r);   
    L= max(L,l);
    R = min(R,r);
}
double Num[4010],x1[110],Y1[110],x2[110],y2[110],
       X[2010],Y[2010],L[2010],R[2010];
int N,M;
bool mark[4010];
int style[1010];
typedef pair<double,int> PII;
set<PII> tim;
set<int> MX;
double
calc(double x0, double y0, double X, double Y)
{
    X -= x0, Y -= y0;
    int i,j,t=0;
    tim.clear();
    for (i = 0; i < N; i++) {
        L[i] = 0, R[i] = 1;
        if (X==0){
            if (x0>=x1[i]&&x0<=x2[i]){
                Unoin(L[i],R[i],calcK(y0,Y,Y1[i]),calcK(y0,Y,y2[i]));
            } else L[i] = R[i] = 0;
        }else if (Y==0){
            if (y0>=Y1[i]&&y0<=y2[i]){
                Unoin(L[i],R[i],calcK(x0,X,x1[i]),calcK(x0,X,x2[i]));
            } else L[i] = R[i] = 0;
        }else 
        {       Unoin(L[i],R[i],calcK(y0,Y,Y1[i]),calcK(y0,Y,y2[i]));
            Unoin(L[i],R[i],calcK(x0,X,x1[i]),calcK(x0,X,x2[i]));
        }
        if (L[i]>=R[i]) continue;
        tim.insert(PII(L[i],~i));
        tim.insert(PII(R[i],i));
    } 
    MX.clear();
    double last = 0,ans = 0;
    for (set<PII>::iterator p = tim.begin();p!=tim.end();p++){

        if (!MX.empty()&&style[*MX.rbegin()]==1) ans+=p->first-last;
        if (p->second<0) MX.insert(~p->second);
        else MX.erase(p->second);
        last = p->first;
    }


    return sqrt((ans*ans)*(X*X+Y*Y));

}
int
main()
{
    int i;
    //freopen("input","r",stdin);
    //freopen("output","w",stdout);
    while (scanf("%d%d", &N, &M) != EOF) {
        for (i = 0; i < N ; i++)
            scanf("%d%lf%lf%lf%lf",&style[i], &x1[i], &Y1[i], &x2[i], &y2[i]);
        double ans = 0;
        for (i = 0; i < M; i++) {
            scanf("%lf%lf", &X[i],&Y[i]);
            if (i>0)
                ans+=calc(X[i-1],Y[i-1],X[i],Y[i]);

        }
        printf("%.2lf\n",ans);
    }
}


}}}

题意是求，在平面上每次对若干个矩形区域依次进行染色和插除操作，然后给出一条折线段，求这个折线段在染色区域内的长度。

出这题的初衷是考察直线点向式的应用，一条直线可以用(x0,y0) + k*(X,Y)表示，其中k就是向量增量的倍数。

k一开始是一个[0,1]的区间，随着限制矩形的增加，区间可以覆盖、延长、擦除，

现在的问题就是，得到每个矩形的区间后，如何区间并和区间擦除。

我用的是扫描线的方法，对于每一段，询问当前最大标号的区间是染色还是擦除，以决定这段是否能计入答案。

代码比较清晰，推荐不会做这题的同学们阅读这篇代码学习。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
map<double,int> mat;
double calcK(double x0,double X,double x1){
    if (X==0) return 0;
    return (x1-x0)/X;
}
double Unoin(double &L,double &R,double l,double r){
    if (l>r) swap(l,r);   
    L= max(L,l);
    R = min(R,r);
}
double Num[4010],x1[110],Y1[110],x2[110],y2[110],
       X[2010],Y[2010],L[2010],R[2010];
int N,M;
bool mark[4010];
int style[1010];
typedef pair<double,int> PII;
set<PII> tim;
set<int> MX;
double
calc(double x0, double y0, double X, double Y)
{
    X -= x0, Y -= y0;
    int i,j,t=0;
    tim.clear();
    for (i = 0; i < N; i++) {
        L[i] = 0, R[i] = 1;
        if (X==0){
            if (x0>=x1[i]&&x0<=x2[i]){
                Unoin(L[i],R[i],calcK(y0,Y,Y1[i]),calcK(y0,Y,y2[i]));
            } else L[i] = R[i] = 0;
        }else if (Y==0){
            if (y0>=Y1[i]&&y0<=y2[i]){
                Unoin(L[i],R[i],calcK(x0,X,x1[i]),calcK(x0,X,x2[i]));
            } else L[i] = R[i] = 0;
        }else 
        {       Unoin(L[i],R[i],calcK(y0,Y,Y1[i]),calcK(y0,Y,y2[i]));
            Unoin(L[i],R[i],calcK(x0,X,x1[i]),calcK(x0,X,x2[i]));
        }
        if (L[i]>=R[i]) continue;
        tim.insert(PII(L[i],~i));
        tim.insert(PII(R[i],i));
    } 
    MX.clear();
    double last = 0,ans = 0;
    for (set<PII>::iterator p = tim.begin();p!=tim.end();p++){
        if (!MX.empty()&&style[*MX.rbegin()]==1) ans+=p->first-last;
        if (p->second<0) MX.insert(~p->second);
        else MX.erase(p->second);
        last = p->first;
    }
    return sqrt((ans*ans)*(X*X+Y*Y));
}
int
main()
{
    int i;
    //freopen("input","r",stdin);
    //freopen("output","w",stdout);
    while (scanf("%d%d", &N, &M) != EOF) {
        for (i = 0; i < N ; i++)
            scanf("%d%lf%lf%lf%lf",&style[i], &x1[i], &Y1[i], &x2[i], &y2[i]);
        double ans = 0;
        for (i = 0; i < M; i++) {
            scanf("%lf%lf", &X[i],&Y[i]);
            if (i>0)
                ans+=calc(X[i-1],Y[i-1],X[i],Y[i]);
        }
        printf("%.2lf\n",ans);
    }
}