CloudLunar
主页
知识库
人文社科
自然科学
跨学科领域
热门分类
算法及题库
云璟月's
墨色集(设计)
指尖集(代码)
未央集(随笔)
流觞集(语录)
如花集(书影)
纸鸢集(小说)
登录
B站
微博
人人
开心
Twitter
Facebook
RSS订阅链接
留言板
关于我
在社交网站上关注我
B站
微博
人人
开心
Twitter
Facebook
RSS订阅
RSS订阅链接
留言板
关于我
查看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}} (AC367) ==题意== 坐标系里一堆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)&¤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; } </pre> |sgu192}}
该页面使用的模板:
模板:=
(
查看源代码
)
模板:信息题
(
查看源代码
)
模板:折叠
(
查看源代码
)
返回
Sgu/192
。
著作权声明
[
编辑
]
除非另有说明,本
网站内容
采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
进行许可(中国大陆可以参照
知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议
,如有不同以前者为准)。
如果需要商业化使用,请另联系作者取得授权。
关于
[
编辑
]
联系
@云璟月Lunar
的新浪微博
本站RSS:
RSS链接