| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| RGB | ★★★★☆ | 答案正确 | 100 | 2015-2-1 17:44:32 | 特殊情况的考虑（0） |
（AC367）
坐标系里一堆RGB三色的线段，投影到x轴上，问RGB三色覆盖到的长度分别为多少（被多种颜色覆盖的时候取最近的）。
（可以算是细节题吧，想起来还行写起来十分恶心）
| 192.cpp代码已折叠
展开折叠内容
|
|---|
#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)&¤tDistanceL<=1e+6)
{
pointColorL[d]+=l[t].color;
}
if(currentDistanceR<minDistanceR)
{
minDistanceR=currentDistanceR;
pointColorR[d]="";
pointColorR[d]+=l[t].color;
}
else if(IsZero(currentDistanceR-minDistanceR)&¤tDistanceR<=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;
}
|
CloudLunar