题目大意：一个小孩不断往地上扔棍子，共n根，求结束后共有多少根不与去他相交。
解法思路：典型的判断线段相交问题，利用快速排斥+双跨立判断相交，最后输出没相交的。
（图片来源：http://www.2cto.com/kf/201308/237246.html）
#include<iostream>
#include<algorithm>
using namespace std;
const int nMax = ;
const int mMax = ;
struct Point
{
double x, y;
}s[nMax], e[nMax];
double mult(Point sp, Point ep, Point op) //叉积
{
return (sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y);
}
bool isInter(Point s1, Point e1, Point s2, Point e2)
{
if( min(s1.x, e1.x) <= max(s2.x, e2.x) &&
min(s1.y, e1.y) <= max(s2.y, e2.y) &&
min(s2.x, e2.x) <= max(s1.x, e1.x) &&
min(s2.y, e2.y) <= max(s1.y, e1.y) && //快速排斥
mult(s2, e2, s1) * mult(s2, e2, e1) <= && //双跨立
mult(s1, e1, s2) * mult(s1, e1, e2) <= )
return true;
return false;
}
int main()
{
int n , i ;
while(scanf("%d", &n) == && n != ) //每当输入一组数据成功
{
int ans[mMax] , m = ;
for(i = ; i <= n; i++)
{
scanf("%lf%lf%lf%lf", &s[i].x, &s[i].y, &e[i].x, &e[i].y);
int pos = -;
for(int j = ; j < m; j ++)
{
if(ans[j] == -)
pos = j;
else
if(isInter(s[i], e[i], s[ans[j]], e[ans[j]]))
ans[j] = -;
}
if(pos == -)
ans[m++] = i;
else
ans[pos] = i;
}
i = ;
sort(ans, ans + m); //升序排列，按照输入顺序
while(ans[i] == -)
i++;
printf("Top sticks:");
while(i < m-)
printf(" %d,", ans[i ++]);
printf(" %d.\n", ans[i]);
}
return ;
}
!!!!这个代码有点问题，但给的两组都过了，求大神指点.....
//这个代码有点问题，但给的两组都过了，求大神指点.....
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
double x,y;
}s,e;
struct side
{
node s,e;
int nth;
}temp;
inline int multy(const node &p0,const node &p1,const node &p2) //叉积
{
return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}
inline bool is_insert(const node &s1,const node &e1,const node &s2,const node &e2) //判交
{
if( min(s1.x, e1.x) <= max(s2.x, e2.x) &&
min(s1.y, e1.y) <= max(s2.y, e2.y) &&
min(s2.x, e2.x) <= max(s1.x, e1.x) &&
min(s2.y, e2.y) <= max(s1.y, e1.y) && //快速排斥
multy(s2, e2, s1) * multy(s2, e2, e1) <= && //双跨立
multy(s1, e1, s2) * multy(s1, e1, e2) <= )
return true;
return false;
}
inline bool cmp(const side &a,const side &b)
{
return (a.nth<b.nth);
}
int main()
{
int n;
while(scanf("%d",&n)==&&n)
{
vector<side>v;
for(int i=;i<n;i++)
{
scanf("%lf%lf%lf%lf",&s.x,&s.y,&e.x,&e.y);
bool f=true,first=true;
for(int j=;j<v.size();j++)
if(is_insert(s,e,v[j].s,v[j].e))
if(first)
v[j].s=s,v[j].e=e,v[j].nth=i,f=false,first=false; //第一次相交替换
else
v.erase(v.begin()+j); //第二次相交直接删
if(f)
{
temp.s=s,temp.e=e,temp.nth=i;
v.push_back(temp);
}
}
sort(v.begin(),v.end(),cmp); //按顺序输出
printf("Top sticks:");
for(int i=;i<v.size()-;i++)
printf(" %d,",v[i].nth+);
v[v.size()-].nth++;
printf(" %d.\n",v[v.size()-].nth); //注意格式
}
return ;
}