Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

被坑了一上午。。。 数据应该有问题!!! 数据没有保证直角 附上代码

Posted by yubin3995 at 2018-08-28 14:04:15 on Problem 3449
//坑了一上午  对拍能过 但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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator