HDOJ(2150) 我的哪错了?C++提交的。跪求代码!!!
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct Node
{
int x,y;
Node operator-(Node &node)
{
Node new_node;
new_node.x=x-node.x;
new_node.y=y-node.y;
return new_node;
}
};
vector<vector<Node> > L;
double cross(Node vec1,Node vec2)
{
return (double)vec1.x*vec2.y-(double)vec1.y*vec2.x;
}
bool straddle(Node n1,Node n2,Node n3,Node n4)
{
Node vec1=n2-n1;
Node vec2=n3-n2;
Node vec3=n4-n2;
if(cross(vec1,vec2)*cross(vec1,vec3)<=0)
return true;
else
return false;
}
double special_straddle(Node n1,Node n2,Node n3,Node n4)
{
Node vec1=n2-n1;
Node vec2=n3-n2;
Node vec3=n4-n2;
return cross(vec1,vec2)*cross(vec1,vec3);
}
bool intersect(vector<vector<Node> > L)
{
int len=L.size();
for(int i=0;i<len-1;i++)
{
for(int m=0;m<L[i].size()-1;m++)
{
for(int j=i+1;j<len;j++)
{
for(int n=0;n<L[j].size()-1;n++)
{
if((m==0&&cross(L[j][n]-L[i][m],L[j][n]-L[j][n+1])==0)||
(m==L[i].size()-2&&cross(L[j][n]-L[i][m+1],L[j][n]-L[j][n+1])==0)||
(n==0&&cross(L[i][m]-L[j][n],L[i][m]-L[i][m+1])==0)||
(n==L[i].size()-2&&cross(L[i][m]-L[j][n+1],L[i][m]-L[i][m+1])==0))
continue;
if(straddle(L[i][m],L[i][m+1],L[j][n],L[j][n+1])&&
straddle(L[j][n],L[j][n+1],L[i][m],L[i][m+1]))
return true;
}
}
}
}
return false;
}
int main()
{
int num,n; //num为管道数,n为每条管道的端点数
vector<Node> p;
while(scanf("%d",&num)!=EOF)
{
L.clear();
Node temp;
for(int i=0;i<num;i++)
{
p.clear();
cin>>n;
for(int j=0;j<n;j++)
{
cin>>temp.x>>temp.y;
p.push_back(temp);
}
L.push_back(p);
}
if(num<=1)
{
cout<<"NO"<<endl;
continue;
}
if(intersect(L))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
[解决办法]
bool intersect(vector<vector<Node> > L)
别的不说,光这一行就饶过你的程序慢了n倍,应该用
bool interset(vector<vector<Node>>& l);
[解决办法]
兄弟,我只能说你太粗心了,输入大小写错误。改了就通过了。代码写的不错,加油,哥已经退役多年了。。。。HDU刚刚进去,好亲切。
[解决办法]
输出,写错了,Yes和No,你懂的。
[解决办法]
加个引用,不会拷贝,类似形参。加还是要加的,不过速度看不出来的。
[解决办法]
嗯,不加的话,每次调用会复制一个L的副本。如果L够大的话(从题目来看应该不算太小), 这个成本还是有点的。好在intersect调用的次数不多,影响未必很明显。不过小处见大,轻忽不得。
[解决办法]
呵呵!good!
[解决办法]
这程序for嵌套的好深啊