| 记录编号 |
275928 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[USACO Open09] 牛类刺绣 |
最终得分 |
100 |
| 用户昵称 |
 Satoshi |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.486 s |
| 提交时间 |
2016-07-03 13:55:33 |
内存使用 |
9.66 MiB |
显示代码纯文本
#include <fstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cstring>
#define N 100010
using namespace std;
typedef long long ll;
typedef double ld;
ifstream cin("cowemb.in");
ofstream cout("cowemb.out");
int n;
ld R;
const ld eps=1e-10,pi=acos(-1.0);
class segment//改段求段的线段树
{
public:
int seg[4*N];
int inc[4*N];
void clear()
{
memset(seg,0,sizeof(seg));
memset(inc,0,sizeof(inc));
}
void pushup(int o)
{
seg[o]=seg[o<<1]+seg[o<<1|1];
}
void pushdown(int o,int l,int r)
{
if(l==r||!inc[o])return ;
int lc=o<<1,rc=lc|1,mid=(l+r)>>1;
seg[lc]+=inc[o]*(mid-l+1);
seg[rc]+=inc[o]*(r-mid);
inc[lc]+=inc[o];
inc[rc]+=inc[o];
inc[o]=0;
}
void add(int o,int l,int r,int ql,int qr,int val)
{
if(ql<=l&&r<=qr)
{
seg[o]+=val*(r-l+1);
inc[o]+=val;
return ;
}
pushdown(o,l,r);
int mid=(l+r)>>1;
if(ql<=mid)add(o<<1,l,mid,ql,qr,val);
if(mid<qr)add(o<<1|1,mid+1,r,ql,qr,val);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return seg[o];
int mid=(l+r)>>1;
int sum=0;
pushdown(o,l,r);
if(ql<=mid)sum=sum+query(o<<1,l,mid,ql,qr);
if(mid<qr)sum=sum+query(o<<1|1,mid+1,r,ql,qr);
return sum;
}
}S;
class interval//区间
{
public:
ld l,r;
}A[N],B[N];
bool operator <(interval a,interval b)//排序按左端点排序
{
if(a.l==b.l)return a.r<b.r;
return a.l<b.l;
}
/*离散化专用*/
map<ld,ld> F;
ld C[2*N],D[2*N];
bool vis[2*N]={0};
void lisanhua()//区间的左、右端点对于左右端点的并数列离散化
{
int i,m=0;
memset(vis,0,sizeof(vis));
memset(C,0,sizeof(C));
memset(D,0,sizeof(D));
F.clear();
for(i=1;i<=n;i++)C[i]=A[i].l;
for(i=1;i<=n;i++)C[n+i]=A[i].r;
sort(C+1,C+2*n+1);
for(i=1;i<2*n;i++)if(C[i]==C[i+1])vis[i]=1;
for(i=1;i<=2*n;i++)if(!vis[i])D[++m]=C[i];
for(i=1;i<=m;i++)F[D[i]]=i;
for(i=1;i<=n;i++)A[i].l=F[A[i].l];
for(i=1;i<=n;i++)A[i].r=F[A[i].r];
}
void read()
{
int i,tot=0;
ld a,b,c,x1,y1,x2,y2,the1,the2;
cin>>n>>R;
for(i=1;i<=n;i++)
{
cin>>a>>b>>c;
if(fabs(c)/sqrt(a*a+b*b)>=R)continue;//圆与直线相离,删除
/*计算圆与直线的交点(x1,y1)和(x2,y2)*/
x1=(-a*c+sqrt(a*a*c*c+(b*b*R*R-c*c)*(a*a+b*b)))/(a*a+b*b);
x2=(-a*c-sqrt(a*a*c*c+(b*b*R*R-c*c)*(a*a+b*b)))/(a*a+b*b);
y1=(-b*c+sqrt(b*b*c*c+(a*a*R*R-c*c)*(a*a+b*b)))/(a*a+b*b);
y2=(-b*c-sqrt(b*b*c*c+(a*a*R*R-c*c)*(a*a+b*b)))/(a*a+b*b);
if(fabs(a*x1+b*y1+c)>eps)swap(y1,y2);
/*计算两个交点相对于原点的极角*/
the1=atan2(y1,x1);
the2=atan2(y2,x2);
/*由atan2转化为真正的极角*/
if(the1<0)the1+=2*pi;
if(the2<0)the2+=2*pi;
/*取劣弧，且使区间的左端点在右端点的逆时针方向*/
if(the1>the2)swap(the1,the2);
if(the2-the1>pi)swap(the1,the2);
tot++;
/*为了方便观察，由弧度制转化为角数制*/
B[tot].l=the1*180/pi;
B[tot].r=the2*180/pi;
}
n=tot;
}
int upperbound(int l,int r,int x)//字面意思，第一个左端点大于等于x的区间的下标
{
int mid;
while(l<r)
{
mid=(l+r)>>1;
if(A[mid].l<=x)l=mid+1;
else r=mid;
}
if(A[l].l<=x)return l+1;
return l;
}
ll cross()//通过线段树求出区间的交点对
{
int i,j,mark=0;
ll sum=0,first,second;
for(i=1;i<=n;i++)A[i]=B[i];
for(i=1;i<=n;i++)if(A[i].l>A[i].r)A[i].r+=360;
sort(A+1,A+n+1);
lisanhua();
S.clear();
for(i=1;i<=n;i++)S.add(1,1,2*n,1,int(A[i].r),1);
for(i=1;i<n;i++)
{
S.add(1,1,2*n,1,int(A[i].r),-1);
first=S.query(1,1,2*n,int(A[i].r),int(A[i].r));
second=n-upperbound(i+1,n,A[i].r)+1;
sum=sum+first-second;
}
for(i=1;i<=n;i++)A[i]=B[i];
for(i=1;i<=n;i++)if(A[i].l>A[i].r)A[i].r+=360;
for(i=1;i<=n;i++)if(A[i].r>=360)
{
A[i].l-=360;
A[i].r-=360;
}
sort(A+1,A+n+1);
for(i=1;i<=n;i++)
{
if(A[i].l<0)mark++;
else break;
}
lisanhua();
S.clear();
for(i=1;i<=n;i++)S.add(1,1,2*n,1,int(A[i].r),1);
for(i=1;i<=mark&&i<n;i++)
{
S.add(1,1,2*n,1,int(A[i].r),-1);
first=S.query(1,1,2*n,int(A[i].r),int(A[i].r));
second=n-upperbound(i+1,n,A[i].r)+1;
sum=sum+first-second;
}
S.clear();
for(i=1;i<=mark;i++)S.add(1,1,2*n,1,int(A[i].r),1);
for(i=1;i<mark;i++)
{
S.add(1,1,2*n,1,int(A[i].r),-1);
first=S.query(1,1,2*n,int(A[i].r),int(A[i].r));
second=mark-upperbound(i+1,mark,A[i].r)+1;
sum=sum-first+second;
}
return sum;
}
void work()
{
ll sum=0;
sum=cross();
cout<<sum<<endl;
}
int main()
{
read();
work();
return 0;
}