另外上一下代码:
#include<iostream>
#include<math.h>
using namespace std;
const long nd=100001;
const double rad=180/3.141592653;
struct marisa
{
double x;
double y;
double d;
};
struct spark
{
double l;
double r;
};
marisa m[nd];
spark s[nd];
double w,h;
long n;
bool equal(double x,double y);
void input();
void swap(long x,long y);
void qsort(long l,long r);
long bomb();
int main()
{
input();
qsort(1,n);
bomb();
return 0;
}
bool equal(double x,double y)
{
double a;
a=x-y;
if(a<=0.001&&a>=-0.001)return true;
else return false;
}
void input()
{
cin>>w>>h>>n;
long a;
double b;
for(a=1;a<=n;a++)
{
cin>>m[a].x>>m[a].y>>m[a].d;
m[a].d/=2;
}
for(a=1;a<=n;a++)
{
b=(h-m[a].y)*tan(m[a].d/rad);
if(m[a].x-b>0.001)s[a].l=m[a].x-b;
else s[a].l=0;
if(m[a].x+b<w)s[a].r=m[a].x+b;
else s[a].r=w;
}
}
void swap(long x,long y)
{
double a;
a=s[x].l;s[x].l=s[y].l;s[y].l=a;
a=s[x].r;s[x].r=s[y].r;s[y].r=a;
}
void qsort(long a1,long a2)
{
long ls,rs;
double mid;
ls=a1;rs=a2;
mid=s[(a2+a1)>>1].l;
while(ls<=rs)
{
while(s[ls].l<mid)ls++;
while(s[rs].l>mid)rs--;
if(ls<=rs)
{
swap(ls,rs);
ls++;rs--;
}
}
if(a1<rs)qsort(a1,rs);
if(ls<a2)qsort(ls,a2);
}
long bomb()
{
long a;
long sum;
long pos;
pos=1;
double left,right;
sum=0;left=0;right=0;
while(true)
{
for(a=pos;a<=n;a++)
{
if((left-s[a].l>=-0.001)&&(right-s[a].r<=0.001))
{
right=s[a].r;
pos=a+1;
}
}
sum++;
if(equal(right,w))break;
if(right==left)
{
cout<<"-1"<<endl;
return 0;
}
left=right;
}
cout<<sum<<endl;
return 0;
}
测试点1 Accepted / 12ms / 7156kB
测试点2 Accepted / 14ms / 7156kB
测试点3 Accepted / 11ms / 7156kB
测试点4 Accepted / 26ms / 7156kB
测试点5 Accepted / 14ms / 7156kB
测试点6 Accepted / 19ms / 7156kB
测试点7 Accepted / 781ms / 7156kB
测试点8 Accepted / 338ms / 7156kB
测试点9 Accepted / 389ms / 7156kB
测试点10 Accepted / 430ms / 7156kB