查看Sgu/192的源代码 ←Sgu/192

[[分类:计算几何‎]][[分类:离散化‎]]
==摘要==
{{信息题|RGB|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}192|4|100|特殊情况的考虑|0|time=2015-2-1 17:44:32}}
==题意==
坐标系里一堆RGB三色的线段，投影到x轴上，问RGB三色覆盖到的长度分别为多少（被多种颜色覆盖的时候取最近的）。
==题解==
#离散化X坐标：首先将所有的端点和交点（O(<m>n^2</m>)）找出来离散化掉，存在数组里（只要X坐标，由于懒直接用了set）。
#按照X坐标遍历每个分段左右极限，可以确定该段的颜色，求和即可。
==代码==
{{折叠|192.cpp代码已折叠
|<pre>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iterator>
#include<iomanip>
#include<set>
#include<string>
#define foreach(it,container) \
    for(typeof((container).begin()) it = (container).begin();it!=(container).end();++it)
using namespace std;
const double INF=1e+7,eps=1e-7,epsL=1e-3;//定义无限//
set<double> setOfX;//X坐标的离散化点集//
const bool IsZero(const double& _x)
{
    return abs(_x)<1e-6;
}
class Vector2//二维向量//
{
public:
    double x,y;
    Vector2(double _x,double _y):x(_x),y(_y){}
    Vector2():x(0),y(0){}
};
double mult(const Vector2 &a, const Vector2 &b, const Vector2 &c)
//叉积模板://
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
bool intersect(const Vector2 &aa, const Vector2 &bb, const Vector2 &cc, const Vector2 &dd)
//相交模板:aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false//
{
    if ( max(aa.x, bb.x)<min(cc.x, dd.x) )
    {
        return false;
    }
    if ( max(aa.y, bb.y)<min(cc.y, dd.y) )
    {
        return false;
    }
    if ( max(cc.x, dd.x)<min(aa.x, bb.x) )
    {
        return false;
    }
    if ( max(cc.y, dd.y)<min(aa.y, bb.y) )
    {
        return false;
    }
    if ( mult(cc, bb, aa)*mult(bb, dd, aa)<0 )
    {
        return false;
    }
    if ( mult(aa, dd, cc)*mult(dd, bb, cc)<0 )
    {
        return false;
    }
    return true;
}
class LineSegment//线段//
{
public:
    Vector2 p1,p2;
    double a,b,c;//所在直线一般式ax+by+c=0//
    char color;
    void init()
    {
        scanf("%lf %lf %lf %lf %c",&p1.x,&p1.y,&p2.x,&p2.y,&color);
        setOfX.insert(p1.x);
        setOfX.insert(p2.x);
        UpdateABC();
    }
    void UpdateABC()
    {
        if(IsZero(p1.x-p2.x))
        {
            a=1,b=0,c=-p1.x;
        }
        else if(IsZero(p1.y-p2.y))
        {
            a=0,b=1,c=-p1.y;
        }
        else
        {
            a=-(p1.y-p2.y)/(p1.x-p2.x);
            b=1;
            c=-(a*p1.x+b*p1.y);
        }
    }
    double getY(const double &_x)
    {
        if(_x+eps>max(p1.x,p2.x)||_x<min(p1.x,p2.x)+eps)
            return INF;
        if(IsZero(b))
            return -c/a;
        return -a*_x/b-c/b;
    }
    friend const Vector2 GetInterPoint(const LineSegment &_l1,const LineSegment &_l2)
    {
        //cout<<"{{:"<<_l1.a<<"x+"<<_l1.b<<"y+"<<_l1.c<<"=0/";
       // cout<<_l2.a<<"x+"<<_l2.b<<"y+"<<_l2.c<<"=0}}\n";
        //fixed:注释忘记去掉//
        double x,y;
        if(IsZero(_l1.a))
            y=-_l1.c/_l1.b;
        else if(IsZero(_l2.a))
            y=-_l2.c/_l2.b;
        else
            y=-(_l1.c/_l1.a-_l2.c/_l2.a)/(_l1.b/_l1.a-_l2.b/_l2.a);
        if(IsZero(_l1.b))
            x=-_l1.c/_l1.a;
        else if(IsZero(_l2.b))
            x=-_l2.c/_l2.a;
        else
            x=-(_l1.c/_l1.b-_l2.c/_l2.b)/(_l1.a/_l1.b-_l2.a/_l2.b);
        return Vector2(x,y);
    }
    friend bool HaveInterPoint(const LineSegment &_l1,const LineSegment &_l2)
    {
        return intersect(_l1.p1,_l1.p2,_l2.p1,_l2.p2);
    }
} l[1000];
char GetSameColor(const string &_a,const string &_b)
{
    if(_a.find('R')!=string::npos&&_b.find('R')!=string::npos)
        return 'R';
    if(_a.find('G')!=string::npos&&_b.find('G')!=string::npos)
        return 'G';
    if(_a.find('B')!=string::npos&&_b.find('B')!=string::npos)
        return 'B';
    return '*';
}
int main()
{
    int N;
    double R(0),G(0),B(0);
    scanf("%d",&N);
    for(int i=1;i<=N;++i)
    {
        l[i].init();
    }
    for(int i=1;i<=N;++i)
        for(int j=i+1;j<=N;++j)
        {
            if(HaveInterPoint(l[i],l[j]))
            {
                Vector2 r=GetInterPoint(l[i],l[j]);
                setOfX.insert(r.x);
               // cout<<"{"<<i<<"<"<<j<<":"<<r.x<<"<"<<r.y<<"}";
            }
        }
    string pointColorL[2],pointColorR[2];
    bool d=1;
    double lastX;
    foreach(i,setOfX)
    {
        d=!d;pointColorL[d]=pointColorR[d]="";
        double minDistanceL=INF,minDistanceR=INF;
        for(int t=1;t<=N;++t)
        {
            double currentDistanceL=l[t].getY(*i-epsL),currentDistanceR=l[t].getY(*i+epsL);
            if(currentDistanceL<minDistanceL)
            {
                minDistanceL=currentDistanceL;
                pointColorL[d]="";
                pointColorL[d]+=l[t].color;
            }
            else if(IsZero(currentDistanceL-minDistanceL)&&currentDistanceL<=1e+6)
            {
                pointColorL[d]+=l[t].color;
            }
            if(currentDistanceR<minDistanceR)
            {
                minDistanceR=currentDistanceR;
                pointColorR[d]="";
                pointColorR[d]+=l[t].color;
            }
            else if(IsZero(currentDistanceR-minDistanceR)&&currentDistanceR<=1e+6)//fixed:加上后半句防止空情况//
            {
                pointColorR[d]+=l[t].color;
            }
        }
        //cout<<"["<<*i<<":"<<pointColorL[d]<<"/"<<pointColorR[d]<<minDistanceR<<"]";
        if(i!=setOfX.begin())
        {
            char c=GetSameColor(pointColorL[d],pointColorR[!d]);
            //fixed:忽略不相叠情形//
            //fixed:重新改用极限方式比较//
            switch(c)
            {
                case 'R':
                    R+=*i-lastX;
                    break;
                case 'G':
                    G+=*i-lastX;
                    break;
                case 'B':
                    B+=*i-lastX;
                    break;
            }
        }
        lastX=*i;
    }
    cout.precision(2);
    cout<<fixed<<"R "<<R<<endl<<"G "<<G<<endl<<"B "<<B<<endl;
}
</pre>
|sgu192}}