| ||||||||||
| 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