Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
被坑了一上午。。。 数据应该有问题!!! 数据没有保证直角 附上代码//坑了一上午 对拍能过 但wa!! //先说说最后的代码 交G++ ac 交C++ ce 尼玛。。 //原来交c++需要手动加string 头文件 不是string.h!! //string的输入流重载是在string中定义的?! iostream干嘛去了。。 //本机改为c++编译器也能过 算了 不扯这些玄学的。。 //由于没注意矩形四点的连边关系WA了一发 但马上就发现了 //至此也只用了1小时多 //关键出错点在于题意没看全 题中保证了矩形数据 中间的点为直角点 //由于没看到这一条件 (right angle原来是直角的意思。。英语背锅) 所以多做了一次判断 //但按常理也不应该错 后来测试估计是真实数据中 出现了中间点不为直角点的情况, 而我进行了判断 进而流程改变了 //由于拿不到真实数据 所以不能下定论 但如果真是数据没按要求给 那就太jb坑了。。。 //费我这么劲写的对拍程序。。。 //如何避免 ?? 看清题意 按出题人的意思走 数据错了至少也能AC //除了TLE 永远不要怀疑cin了!!! //eps取1e-8没问题 不用怀疑 //不用老怀疑 读入输出问题 #include<iostream> #include<math.h> #include<string.h> #include<vector> #include<algorithm> #include<stdio.h> using namespace std; const bool _debug = 0; #define outl(_x) if(_debug)cout<<#_x" = "<<(_x)<<endl; #define out(_x) if(_debug)cout<<#_x" = "<<(_x)<<' '; #define dbg if(_debug){cout<<"debug at line:"<<__LINE__<<endl;} #define outs(_a,_n) if(_debug){cout<<#_a"[] = ";fo(_i,0,_n)cout<<_a[_i]<<' ';cout<<endl;} #define outss(_a,_m,_n) if(_debug){cout<<#_a"[] = \n";fo(_i,0,_m){fo(_j,0,_n)cout<<_a[_i][_j]<<' ';cout<<endl;}} #define clr(_s,_a) memset(_s,_a,sizeof(_s)); #define fo(_i,_s,_t) for(int _i=_s;_i<_t;_i++) #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); typedef long long ll; const double eps = 1e-8; const double PI = acos(-1.0); int sgn(double x) { if(fabs(x) < eps)return 0; if(x < 0)return -1; else return 1; } struct Point { double x,y; Point() {} Point(double _x,double _y) { x = _x; y = _y; } Point operator -(const Point &b)const { return Point(x - b.x,y - b.y); } Point operator +(const Point &b)const { return Point(x + b.x,y + b.y); } //叉积 double operator ^(const Point &b)const { return x*b.y - y*b.x; } //点积 double operator *(const Point &b)const { return x*b.x + y*b.y; } //绕原点旋转角度B(弧度值),后x,y的变化 void transXY(double B) { double tx = x,ty = y; x = tx*cos(B) - ty*sin(B); y = tx*sin(B) + ty*cos(B); } void print(){ if(_debug){ cout<<"("<<x<<","<<y<<")"<<endl; } } }; typedef Point Vector; struct Line { Point s,e; Line() {} Line(Point _s,Point _e) { s = _s; e = _e; } //两直线相交求交点 //第一个值为0表示直线重合,为1表示平行,为2是相交 //只有第一个值为2时,交点才有意义 pair<int,Point> operator &(const Line &b)const { Point res = s; if(sgn((s-e)^(b.s-b.e)) == 0) { if(sgn((s-b.e)^(b.s-b.e)) == 0) return make_pair(0,res);//重合 else return make_pair(1,res);//平行 } double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e)); res.x += (e.x-s.x)*t; res.y += (e.y-s.y)*t; return make_pair(2,res); } void print(){ if(_debug){ cout<<"("<<s.x<<","<<s.y<<")-->("<<e.x<<","<<e.y<<")"<<endl; } } }; //*两点间距离 double dist(Point a,Point b) { return sqrt((a-b)*(a-b)); } //*判断线段相交 bool inter(Line l1,Line l2) { return max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) && max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) && max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) && max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) && sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 && sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0; } //判断直线和线段相交 bool SegInterLine(Line l1,Line l2) { //判断直线l1和线段l2是否相交 return sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0; } //点到直线距离 //返回为result,是点到直线最近的点 Point PointToLine(Point P,Line L) { Point result; double t = ((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s)); result.x = L.s.x + (L.e.x-L.s.x)*t; result.y = L.s.y + (L.e.y-L.s.y)*t; return result; } //点到线段的距离 //返回点到线段最近的点 Point NearestPointToLineSeg(Point P,Line L) { Point result; double t = ((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s)); if(t >= 0 && t <= 1) { result.x = L.s.x + (L.e.x - L.s.x)*t; result.y = L.s.y + (L.e.y - L.s.y)*t; } else { if(dist(P,L.s) < dist(P,L.e)) result = L.s; else result = L.e; } return result; } //计算多边形面积 //点的编号从0~n-1 double CalcArea(Point p[],int n) { double res = 0; for(int i = 0; i < n; i++) res += (p[i]^p[(i+1)%n])/2; return fabs(res); } //*判断点在线段上 bool OnSeg(Point P,Line L) { return sgn((L.s-P)^(L.e-P)) == 0 && sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 && sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0; } //*判断点在凸多边形内 //点形成一个凸包,而且按逆时针排序(如果是顺时针把里面的<0改为>0) //点的编号:0~n-1 //返回值: //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inConvexPoly(Point a,Point p[],int n) { for(int i = 0; i < n; i++) { if(sgn((p[i]-a)^(p[(i+1)%n]-a)) < 0)return -1; else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0; } return 1; } //*判断点在任意多边形内 //射线法,poly[]的顶点数要大于等于3,点的编号0~n-1 //返回值 //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inPoly(Point p,Point poly[],int n) { int cnt; Line ray,side; cnt = 0; ray.s = p; ray.e.y = p.y; ray.e.x = -100000000000.0;//-INF,注意取值防止越界 for(int i = 0; i < n; i++) { side.s = poly[i]; side.e = poly[(i+1)%n]; if(OnSeg(p,side))return 0; //如果平行轴则不考虑 if(sgn(side.s.y - side.e.y) == 0) continue; if(OnSeg(side.s,ray)) { if(sgn(side.s.y - side.e.y) > 0)cnt++; } else if(OnSeg(side.e,ray)) { if(sgn(side.e.y - side.s.y) > 0)cnt++; } else if(inter(ray,side)) cnt++; } if(cnt % 2 == 1)return 1; else return -1; } //判断凸多边形 //允许共线边 //点可以是顺时针给出也可以是逆时针给出 //点的编号1~n-1 bool isConvex(Point poly[],int n) { bool s[3]; memset(s,false,sizeof(s)); for(int i = 0; i < n; i++) { s[sgn( (poly[(i+1)%n]-poly[i])^(poly[(i+2)%n]-poly[i]) )+1] = true; if(s[0] && s[2])return false; } return true; } char tps1[111],tps2[111],tps3[111],tps[111][111]; string c,cmd;//,tps1,tps2,tps3,tps[111]; int x1,x2,y11,y2,x3,y3,x[111],y[111],n; typedef vector<Line> ls; typedef pair<string,ls> bkt; vector<bkt> bk; ls fun(Point p1,Point p2){ Point p0,p3,p4; p0.x=(p1.x+p2.x)/2; p0.y=(p1.y+p2.y)/2; Point v1=p1-p0; Point v2=p1-p0; v1.transXY(PI/2); p3=p0+v1; v2.transXY(3*PI/2); p4=p0+v2; ls pls; pls.push_back(Line(p1,p4)); pls.push_back(Line(p4,p2)); pls.push_back(Line(p2,p3)); pls.push_back(Line(p3,p1)); fo(i,0,4) pls[i].print(); return pls; } bool ck(Point p1,Point p2,Point p3){ if(sgn((p3-p1)*(p2-p1))==0)return 1; return 0; } ls fun2(Point p1,Point p2,Point p3){ Point p4=p1+p3-p2; /*if(ck(p2,p1,p3)){ swap(p3,p2); } else if(ck(p1,p2,p3)){ p4=p2+p3-p1; swap(p1,p3); } else if(ck(p3,p1,p2)){ p4=p1+p2-p3; swap(p3,p3); }*/ ls pls; pls.push_back(Line(p1,p4)); pls.push_back(Line(p4,p3)); pls.push_back(Line(p3,p2)); pls.push_back(Line(p2,p1)); return pls; } bool ck2(ls ls1,ls ls2){ fo(i,0,ls1.size()) fo(j,0,ls2.size()){ if(inter(ls1[i],ls2[j])) return 1; } return 0; } bool cmp(bkt e1,bkt e2){return e1.first.compare(e2.first)<0;}; int main(){ FAST; while(cin>>c){ if(c.compare(".")==0)break; //outl(c) //dbg if(c=="-"){ sort(bk.begin(),bk.end(),cmp); fo(i,0,bk.size()){ vector<string>ans; fo(j,0,bk.size()){ if(i!=j&&ck2(bk[i].second,bk[j].second)) ans.push_back(bk[j].first); } if(ans.size()==0){ cout<<bk[i].first<<" has no intersections\n"; } else{ if(ans.size()==1) cout<<bk[i].first<<" intersects with "<<ans[0]<<endl; if(ans.size()==2) cout<<bk[i].first<<" intersects with "<<ans[0]<<" and "<<ans[1]<<endl; if(ans.size()>=3){ cout<<bk[i].first<<" intersects with "; fo(k,0,ans.size()-1) cout<<ans[k]<<", "; cout<<"and "<<ans[ans.size()-1]<<endl; } } } cout<<endl; bk.clear(); continue; } cin>>cmd; //outl(cmd) if(cmd=="square"){ //dbg cin>>tps1>>tps2; //outl(tps1) //outl(tps2) //dbg sscanf(tps1,"(%d,%d)",&x1,&y11); sscanf(tps2,"(%d,%d)",&x2,&y2); bk.push_back(make_pair(c,fun(Point(x1,y11),Point(x2,y2)))); } if(cmd=="line"){ cin>>tps1>>tps2; sscanf(tps1,"(%d,%d)",&x1,&y11); sscanf(tps2,"(%d,%d)",&x2,&y2); ls pls; pls.push_back(Line(Point(x1,y11),Point(x2,y2))); bk.push_back(make_pair(c,pls)); } if(cmd=="polygon"){ cin>>n; fo(i,0,n){ cin>>tps[i]; sscanf(tps[i],"(%d,%d)",&x[i],&y[i]); } ls pls; fo(i,0,n-1){ pls.push_back(Line(Point(x[i],y[i]),Point(x[i+1],y[i+1]))); } pls.push_back(Line(Point(x[0],y[0]),Point(x[n-1],y[n-1]))); bk.push_back(make_pair(c,pls)); } if(cmd=="triangle"){ cin>>tps1>>tps2>>tps3; sscanf(tps1,"(%d,%d)",&x1,&y11); sscanf(tps2,"(%d,%d)",&x2,&y2); sscanf(tps3,"(%d,%d)",&x3,&y3); ls pls; pls.push_back(Line(Point(x1,y11),Point(x2,y2))); pls.push_back(Line(Point(x1,y11),Point(x3,y3))); pls.push_back(Line(Point(x2,y2),Point(x3,y3))); bk.push_back(make_pair(c,pls)); } if(cmd=="rectangle"){ cin>>tps1>>tps2>>tps3; sscanf(tps1,"(%d,%d)",&x1,&y11); sscanf(tps2,"(%d,%d)",&x2,&y2); sscanf(tps3,"(%d,%d)",&x3,&y3); bk.push_back(make_pair(c,fun2(Point(x1,y11),Point(x2,y2),Point(x3,y3)))); } outl(bk.size()) } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator