首页 > ACM题库 > HDU-杭电 > HDU 3465-Life is a Line[解题报告]HOJ
2014
03-30

HDU 3465-Life is a Line[解题报告]HOJ

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 . 谁能解释下?