http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11353
#include<iostream>
#include<stdio.h>
#include<string>
#include<math.h>
#define PI acos(-1)
//using namespace std;
struct Nod
{
int dir;
int len;
}node[];
struct Point
{
double x;
double y;
};
struct segmemt
{
Point s;
Point t;
};
double MAX(double a,double b)
{
if(a>b)return a;
return b;
}
double MIN(double a,double b)
{
if(a<b)return a;
return b;
}
double mulpti(Point ps , Point pe , Point p)
{
return (pe.x-ps.x)*(p.y-ps.y)-(p.x-ps.x)*(pe.y-ps.y);
}
bool inser(Point p1, Point p2 , Point p3, Point p4) //判断线段是否相交
{
if(MAX(p1.x,p2.x)>=MIN(p3.x,p4.x) &&
MAX(p3.x,p4.x)>=MIN(p1.x,p2.x) &&
MAX(p1.y,p2.y)>=MIN(p3.y,p4.y) &&
MAX(p3.y,p4.y)>=MIN(p1.y,p2.y) &&
mulpti(p1,p2,p3)*mulpti(p1,p2,p4)<= &&
mulpti(p3,p4,p1)*mulpti(p3,p4,p2)<=)
return true; //相交
else
return false; //不相交
} //得到向量的x坐标
double getX(double x,double y,int dir) //传入(x,y)向量以及角度dir
{
return x*cos(dir/180.0*PI)-y*sin(dir/180.0*PI);
}
//得到向量的y坐标
double getY(double x,double y,int dir)
{
return y*cos(dir/180.0*PI)+x*sin(dir/180.0*PI);
} int main()
{
int n;
segmemt list[];
while(~scanf("%d",&n)&&n)
{
int i;
double x,y,tx,ty;
for(i=;i<n;i++)
{
scanf("%d%d",&node[i].dir,&node[i].len);
if(node[i].dir<) node[i].dir=+node[i].dir;
}
list[].s.x=;
list[].s.y=;
x = getX(,,node[].dir);
y = getY(,,node[].dir);
list[].t.x = x*node[].len;
list[].t.y = y*node[].len;
for(i=;i<n;i++)
{
list[i].s.x = list[i-].t.x;
list[i].s.y = list[i-].t.y;
tx = x;
ty = y;
x = getX(tx,ty,node[i].dir);
y = getY(tx,ty,node[i].dir);
list[i].t.x = x*node[i].len + list[i].s.x;
list[i].t.y = y*node[i].len + list[i].s.y;
}
int j,flag=;
for(i=;i<n;i++)
{
for(j=;j<=i-;j++)
{
if(inser(list[j].s,list[j].t,list[i].s,list[i].t))
{
flag = ;
printf("%d\n",i+);
break;
}
}
if(flag) break;
}
if(!flag)
{
puts("SAFE");
}
}
return ;
}