team2012-F3-sol-0011

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定一条m个折点的折线和n个矩形操作，每个操作是涂色或者擦除颜色，问最后剩余的带色折线段长度是多少。
解法：对于这个折线的每一段进行计算，最后合并起来就是总长度。
将线段与矩形的相交部分用一个区间(l, r)表示，按zYc学长的方法，可以将其全部化到(0, 1)之间。
判断出线段与矩形的相交部分后，将这n个相交部分形成的线段求交，并且进行染色操作
O(n^2)的求交就可以过，就是暴力判断一下相邻两个点在哪个序号最大的线段中。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <utility>
#include <set>
using namespace std;
typedef pair<double, double> PDD;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}

const int MAXN = 1003;
int n, m, f[MAXN * 2];
PDD seg[MAXN];
struct r
{
    int type;
    double x1, x2, y1, y2;
}rec[MAXN];

PDD get_seg(int w, double x1, double y1, double x2, double y2)
{
    if(x1 == x2)
    {
        if(y1 > y2) swap(y1, y2);
        if(x1 < rec[w].x1 || x1 > rec[w].x2 || y2 <= rec[w].y1 || y1 >= rec[w].y2)  return PDD(0, 0);
        double ly = max(y1, rec[w].y1), ry = min(y2, rec[w].y2);
        return PDD((ly - y1) / (y2 - y1), (ry - y1) / (y2 - y1));
    }
    if(y1 == y2)
    {
        if(x1 > x2) swap(x1, x2);
        if(y1 < rec[w].y1 || y1 > rec[w].y2 || x2 <= rec[w].x1 || x1 >= rec[w].x2)  return PDD(0, 0);
        double lx = max(x1, rec[w].x1), rx = min(x2, rec[w].x2);
        return PDD((lx - x1) / (x2 - x1), (rx - x1) / (x2 - x1));
    }
    if(x1 > x2)
        swap(x1, x2), swap(y1, y2);
    double lx = max(x1, rec[w].x1), rx = min(x2, rec[w].x2);
    if(lx >= rx)    return PDD(0, 0);
    double dx = x2 - x1, dy = y2 - y1,
           k = dy / dx, ly, ry;
    if(k > 0)
        ly = y1 + (lx - x1) * k, ry = y1 + (rx - x1) * k;
    else
        ry = y1 + (lx - x1) * k, ly = y1 + (rx - x1) * k;
    ly = max(ly, rec[w].y1);
    ry = min(ry, rec[w].y2);
    if(ly >= ry)    return PDD(0, 0);
    if(k > 0)
        return PDD((ly - y1) / dy, (ry - y1) / dy);
    else
        return PDD((ry - y1) / dy, (ly - y1) / dy);
}

double dis(double x1, double y1, double x2, double y2)
{
    double dx = x1 - x2, dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}

double gao(double x1, double y1, double x2, double y2)
{
    vector<double> pts;
    set<double> rep;
    for(int i = 1; i <= n; i++)
    {
        seg[i] = get_seg(i, x1, y1, x2, y2);
        if(seg[i].first >= seg[i].second)   seg[i] = PDD(0, 0);
        if(!rep.count(seg[i].first))
            rep.insert(seg[i].first), pts.push_back(seg[i].first);
        if(!rep.count(seg[i].second))
            rep.insert(seg[i].second), pts.push_back(seg[i].second);
    }
    sort(pts.begin(), pts.end());

    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i++)
    {
        double l = seg[i].first, r = seg[i].second,
               pre = pts[0], now;
        for(int j = 1; j < pts.size(); j++, pre = now)
        {
            now = pts[j];
            if(pre >=l && pre <= r && now >= l && now <= r)
                takemax(f[j], i);
        }
    }

    double ret = 0;
    for(int i = 1; i < pts.size(); i++)
        if(f[i] && rec[f[i]].type)
            ret += pts[i] - pts[i-1];

    return ret * dis(x1, y1, x2, y2);
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        for(int i = 1; i <= n; i++)
            scanf("%d %lf %lf %lf %lf", &rec[i].type, &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);
        double x, y, lx, ly, ans = 0;
        for(int i = 1; i <= m; i++, lx = x, ly = y)
        {
            scanf("%lf %lf", &x, &y);
            if(i >= 2)  ans += gao(lx, ly, x, y);
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}
}}}

题意：给定一条m个折点的折线和n个矩形操作，每个操作是涂色或者擦除颜色，问最后剩余的带色折线段长度是多少。
解法：对于这个折线的每一段进行计算，最后合并起来就是总长度。
将线段与矩形的相交部分用一个区间(l, r)表示，按zYc学长的方法，可以将其全部化到(0, 1)之间。
判断出线段与矩形的相交部分后，将这n个相交部分形成的线段求交，并且进行染色操作
O(n^2)的求交就可以过，就是暴力判断一下相邻两个点在哪个序号最大的线段中。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <utility>
#include <set>
using namespace std;
typedef pair<double, double> PDD;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}
const int MAXN = 1003;
int n, m, f[MAXN * 2];
PDD seg[MAXN];
struct r
{
    int type;
    double x1, x2, y1, y2;
}rec[MAXN];
PDD get_seg(int w, double x1, double y1, double x2, double y2)
{
    if(x1 == x2)
    {
        if(y1 > y2) swap(y1, y2);
        if(x1 < rec[w].x1 || x1 > rec[w].x2 || y2 <= rec[w].y1 || y1 >= rec[w].y2)  return PDD(0, 0);
        double ly = max(y1, rec[w].y1), ry = min(y2, rec[w].y2);
        return PDD((ly - y1) / (y2 - y1), (ry - y1) / (y2 - y1));
    }
    if(y1 == y2)
    {
        if(x1 > x2) swap(x1, x2);
        if(y1 < rec[w].y1 || y1 > rec[w].y2 || x2 <= rec[w].x1 || x1 >= rec[w].x2)  return PDD(0, 0);
        double lx = max(x1, rec[w].x1), rx = min(x2, rec[w].x2);
        return PDD((lx - x1) / (x2 - x1), (rx - x1) / (x2 - x1));
    }
    if(x1 > x2)
        swap(x1, x2), swap(y1, y2);
    double lx = max(x1, rec[w].x1), rx = min(x2, rec[w].x2);
    if(lx >= rx)    return PDD(0, 0);
    double dx = x2 - x1, dy = y2 - y1,
           k = dy / dx, ly, ry;
    if(k > 0)
        ly = y1 + (lx - x1) * k, ry = y1 + (rx - x1) * k;
    else
        ry = y1 + (lx - x1) * k, ly = y1 + (rx - x1) * k;
    ly = max(ly, rec[w].y1);
    ry = min(ry, rec[w].y2);
    if(ly >= ry)    return PDD(0, 0);
    if(k > 0)
        return PDD((ly - y1) / dy, (ry - y1) / dy);
    else
        return PDD((ry - y1) / dy, (ly - y1) / dy);
}
double dis(double x1, double y1, double x2, double y2)
{
    double dx = x1 - x2, dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}
double gao(double x1, double y1, double x2, double y2)
{
    vector<double> pts;
    set<double> rep;
    for(int i = 1; i <= n; i++)
    {
        seg[i] = get_seg(i, x1, y1, x2, y2);
        if(seg[i].first >= seg[i].second)   seg[i] = PDD(0, 0);
        if(!rep.count(seg[i].first))
            rep.insert(seg[i].first), pts.push_back(seg[i].first);
        if(!rep.count(seg[i].second))
            rep.insert(seg[i].second), pts.push_back(seg[i].second);
    }
    sort(pts.begin(), pts.end());
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i++)
    {
        double l = seg[i].first, r = seg[i].second,
               pre = pts[0], now;
        for(int j = 1; j < pts.size(); j++, pre = now)
        {
            now = pts[j];
            if(pre >=l && pre <= r && now >= l && now <= r)
                takemax(f[j], i);
        }
    }
    double ret = 0;
    for(int i = 1; i < pts.size(); i++)
        if(f[i] && rec[f[i]].type)
            ret += pts[i] - pts[i-1];
    return ret * dis(x1, y1, x2, y2);
}
int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        for(int i = 1; i <= n; i++)
            scanf("%d %lf %lf %lf %lf", &rec[i].type, &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);
        double x, y, lx, ly, ans = 0;
        for(int i = 1; i <= m; i++, lx = x, ly = y)
        {
            scanf("%lf %lf", &x, &y);
            if(i >= 2)  ans += gao(lx, ly, x, y);
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}