zoj 3157 Weapon

zoj 3157 Weapon

#include<cstdio>#include<iostream>#include<algorithm>#include<string.h>#include<map>#define eps 1e-6using namespace std;struct node{double a,b;int i;}K[10010];struct node2{int a,b,i;}V[10010];struct tree{ int l,r,s;}A[40010];int N;double x1[10010],x2[10010],y1[10010],y2[10010];bool cmp1(node a,node b){ return a.a<b.a;}bool cmp2(node a,node b){ return a.b<b.b;}bool cmp3(node2 a,node2 b){ if(a.a==b.a) return a.b>b.b; return a.a<b.a;}void build(int n,int l,int r){ A[n].l=l;A[n].r=r;A[n].s=0; if(l==r) return ; int mid=(l+r)/2; build(2*n,l,mid); build(2*n+1,mid+1,r);}void change(int n,int j){ A[n].s++; if(A[n].l==A[n].r) return ; int mid=(A[n].l+A[n].r)/2; if(j<=mid) change(2*n,j); else change(2*n+1,j);}int search(int n,int l,int r){ if(A[n].l==l&&A[n].r==r) return A[n].s; int mid=(A[n].l+A[n].r)/2; if(r<=mid) return search(2*n,l,r); else if(l>mid) return search(2*n+1,l,r); return search(2*n,l,mid)+search(2*n+1,mid+1,r);}int main(){ int i,j,k,l; int n,m; double s,t; int a,b; int sav; while(scanf("%d",&N)!=EOF) { for(i=0;i<N;i++) { scanf("%lf%lf%lf%lf",x1+i,y1+i,x2+i,y2+i); } scanf("%lf%lf",&s,&t); for(i=0;i<N;i++) { K[i].i=i;V[i].i=i+1; K[i].a=(y2[i]*t-y2[i]*x1[i]-y1[i]*t+y1[i]*x2[i])/(x2[i]-x1[i]); K[i].b=(y2[i]*s-y2[i]*x1[i]-y1[i]*s+y1[i]*x2[i])/(x2[i]-x1[i]); } sort(K,K+N,cmp1); k=1; for(i=0;i<N;i++) { j=i; while(K[i+1].a<K[i].a+eps&&i<N-1) i++; for(l=j;l<=i;l++) { V[K[l].i].a=k; }k++; }n=k; sort(K,K+N,cmp2); k=1; for(i=0;i<N;i++) { j=i; while(K[i+1].b<K[i].b+eps&&i<N-1) i++; for(l=j;l<=i;l++) { V[K[l].i].b=k; }k++; }m=k; for(i=0;i<N;i++) { V[i].b=m-V[i].b; } sort(V,V+N,cmp3); build(1,1,m-1); sav=0; for(i=0;i<N;i++) { if(V[i].b!=1) sav+=search(1,1,V[i].b-1); change(1,V[i].b); } printf("%dn",sav); } return 0;}