2014
03-30

Life is a Line

There is a saying: Life is like a line, some people are your parallel lines, while others are destined to meet you.
Maybe have met, maybe just a matter of time, two unparallel lines will always meet in some places, and now a lot of life (i.e. line) are in the same coordinate system, in a given open interval, how many pairs can meet each other?

There are several test cases in the input.

Each test case begin with one integer N (1 ≤ N ≤ 50000), indicating the number of different lines.
Then two floating numbers L, R follow (-10000.00 ≤ L < R ≤ 10000.00), indicating the interval (L, R).
Then N lines follow, each line contains four floating numbers x1, y1, x2, y2 (-10000.00 ≤ x1, y1, x2, y2 ≤ 10000.00), indicating two different points on the line. You can assume no two lines are the same one.

The input terminates by end of file marker.

There are several test cases in the input.

Each test case begin with one integer N (1 ≤ N ≤ 50000), indicating the number of different lines.
Then two floating numbers L, R follow (-10000.00 ≤ L < R ≤ 10000.00), indicating the interval (L, R).
Then N lines follow, each line contains four floating numbers x1, y1, x2, y2 (-10000.00 ≤ x1, y1, x2, y2 ≤ 10000.00), indicating two different points on the line. You can assume no two lines are the same one.

The input terminates by end of file marker.

3
0.0 1.0
0.0 0.0 1.0 1.0
0.0 2.0 1.0 2.0
0.0 2.5 2.5 0.0

1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define NN 101000
#define eps (1e-10)

int n,totl,tl1,i,tr,ttr;
double lb,rb;

struct point {double x,y;}p[NN];
struct line{
point s,e;double l,r;int val;
void getlr(double lb,double rb){
l=s.y+(s.y-e.y)/(s.x-e.x)*(lb-s.x);
r=s.y+(s.y-e.y)/(s.x-e.x)*(rb-s.x);
}
}l[NN];

int c[NN];
double svr[NN];

inline int query(int x){
int ret=0;
while(x){
ret+=c[x];
x-=lowbit(x);
}
return ret;
}

inline void update(int x,int val){
while(x<=ttr){
c[x]+=val;
x+=lowbit(x);
}
}
int cmp2(double a,double b){
return a<b;
}

int cmp1(line a,line b){
//if (fabs(a.l-b.l)<eps) return a.r>b.r;
//else return a.l<b.l;
if (fabs(a.l-b.l)<eps) return a.r>b.r;
return a.l>b.l;
}

int bsch(int l,int r,double val){
int mid;
while(l<=r){
mid=(l+r)/2;
if (fabs(val-svr[mid])<eps){
return mid;
}
if (val>svr[mid]) l=mid+1;
else r=mid-1;
}
//cout<<"fuck!"<<endl;
while(1);
}

int main(){

while(scanf("%d",&n)!=EOF){
scanf("%lf%lf",&lb,&rb);
totl=0;
tl1=0;
for(i=1;i<=n;++i){
totl++;
scanf("%lf%lf%lf%lf",&l[totl].s.x,&l[totl].s.y,&l[totl].e.x,&l[totl].e.y);
if (fabs(l[totl].s.x-l[totl].e.x)<=eps){
if (l[totl].s.x<=rb-eps&&l[totl].s.x>=lb+eps) tl1++;
totl--;
}

}

for(i=1;i<=totl;++i){
l[i].getlr(lb,rb);
}
tr=0;
for(i=1;i<=totl;++i){
svr[++tr]=l[i].r;
}
sort(svr+1,svr+tr+1,cmp2);

ttr=1;
for(i=2;i<=tr;++i){
if (fabs(svr[i]-svr[i-1])>eps) svr[++ttr]=svr[i];
}
//for(i=1;i<=ttr;++i) printf(" %lf\n",svr[i]);
for(i=1;i<=totl;++i){
l[i].val=bsch(1,ttr,l[i].r);
}
sort(l+1,l+totl+1,cmp1);
memset(c,0,sizeof(c));
long long ans=0;
for(i=1;i<=totl;++i){
//printf(" %lf %d\n",l[i].l,l[i].val);
ans=ans+query(l[i].val-1);
update(l[i].val,1);
//if (i>1&&l[i].l==l[i])
}
ans=ans+(long long)tl1*totl;
printf("%I64d\n",ans);
}
return 0;
}

1. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

3. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？