当前位置:首页 » Project Euler » 详细页

Intersections 题号:165 难度: 65 中英对照

A segment is uniquely defined by its two endpoints.
By considering two line segments in plane geometry there are three possibilities:
the segments have zero points, one point, or infinitely many points in common.

Moreover when two segments have exactly one point in common it might be the case that that common point is an endpoint of either one of the segments or of both. If a common point of two segments is not an endpoint of either of the segments it is an interior point of both segments.
We will call a common point T of two segments L1 and L2 a true intersection point of L1 and L2 if T is the only common point of L1 and L2 and T is an interior point of both segments.

Consider the three segments L1, L2, and L3:

L1: (27, 44) to (12, 32)
L2: (46, 53) to (17, 62)
L3: (46, 70) to (22, 40)

It can be verified that line segments L2 and L3 have a true intersection point. We note that as the one of the end points of L3: (22,40) lies on L1 this is not considered to be a true point of intersection. L1 and L2 have no common point. So among the three line segments, we find one true intersection point.

Now let us do the same for 5000 line segments. To this end, we generate 20000 numbers using the so-called "Blum Blum Shub" pseudo-random number generator.

s0 = 290797

sn+1 = sn×sn (modulo 50515093)

tn = sn (modulo 500)

To create each line segment, we use four consecutive numbers tn. That is, the first line segment is given by:

(t1, t2) to (t3, t4)

The first four numbers computed according to the above generator should be: 27, 144, 12 and 232. The first segment would thus be (27,144) to (12,232).

How many distinct true intersection points are found among the 5000 line segments?

Solution

按照题目要求进行暴力枚举即可。 需要注意的是: 1. 由于所有点坐标都是有理数,所以需要模拟有理数的运算。如果单纯使用double型,精度不够。 2. 去重需要使用TreeSet,而不能使用HashSet,后者有Hash冲突,会导致错误。

Code

import java.util.*;

public final class p165 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    static public String run() {
    	Segment[] segs=new Segment[5000];
    	final long mod=50515093;
    	long s=290797;
    	for(int i=1;i<=5000;i++){
    		long a=s*s%mod;
    		long b=a*a%mod;
    		long c=b*b%mod;
    		long d=c*c%mod;
    		segs[i-1]=new Segment(new D(a%500),new D(b%500),new D(c%500),new D(d%500));
    		s=d;
    	}
    	TreeMap<Point,Object> ans=new TreeMap<Point,Object>();
    	for(int i=0;i<5000;i++){
    		for(int j=i+1;j<5000;j++){
    			Segment a=segs[i],b=segs[j];
    			Point p=a.cross(b);
    			if(p.x.compareTo(new D(500))>0) continue;
    			if(a.on(p) && b.on(p)){
    				ans.put(p,null);
    			}
    		}
    	}
		return ""+ans.size();
	}
    public static long gcd(long i, long j) {  
    	long k;   
        while ((k=i%j) != 0) {            
            i = j;  
            j = k;  
        }  
        return j;  
    }  
    static class D implements Comparable<D>{
    	long p,q;// p/q
    	D(long p){this.p=p;this.q=1;}
    	D(long p,long q){
    		if(q<0){
    			p=-p;q=-q;
    		}
    		if(q==0){
    			System.out.println("???");
    		}
    		long g=gcd(p,q);
    		this.p=p/g;this.q=q/g;
    	}
    	public D abs(){
    		return new D(Math.abs(p),Math.abs(q));
    	}
    	public int compareTo(D d){
    		if(q*d.q>0) return Long.compare(p*d.q,d.p*q);
    		else return Long.compare(d.p*q,p*d.q);
    	}
    	public D sub(D d){
    		return new D(p*d.q-d.p*q,q*d.q);
    	}
    	public D mul(D d){
    		return new D(p*d.p,q*d.q);
    	}
    	public D add(D d){
    		return new D(p*d.q+d.p*q,q*d.q);
    	}
    	public D dao(){
    		return new D(q,p);
    	}
    }
    static class Point implements Comparable<Point>{
    	D x,y;
    	Point(D a,D b){x=a;y=b;}
    	public boolean equals(Object o){
    		if(o==null) return false;
    		if(o instanceof Point) if(cmp(x,((Point) o).x)==0 && cmp(y,((Point) o).y)==0)
    			return true;
    		return false;
    	}
    	public int compareTo(Point p){
    		if(cmp(x,p.x)==0) return cmp(y,p.y);
    		return cmp(x,p.x);
    	}
    	public Point to(Point p){
    		return new Point(p.x.sub(x),p.y.sub(y));
    	}
    	public D cross(Point p){
    		return x.mul(p.y).sub(y.mul(p.x));
    	}
    	public D abs(){
    		return x.mul(x).add(y.mul(y));
    	}
    }
    static int cmp(D a,D b){
    	return a.compareTo(b);
    }
    static final D zero=new D(0);
    static class Segment{
    	Point s,e;
    	D a,b,c;
    	Segment(D a,D b,D c,D d){
    		s=new Point(a,b);
    		e=new Point(c,d);
    		this.a=s.y.sub(e.y);
    		this.b=e.x.sub(s.x);
    		this.c=s.x.mul(e.y).sub(e.x.mul(s.y));
    	}
    	Point cross(Segment seg){
    		Point res=new Point(new D(555),new D(555));
    		D A=seg.a,B=seg.b,C=seg.c;
    		D Q;
    		if(cmp((Q=A.mul(b).sub(a.mul(B))),zero)!=0)
    			res.y=(a.mul(C).sub(A.mul(c))).mul(Q.dao());
    			if(cmp(a,zero)!=0) res.x=zero.sub(b.mul(res.y).add(c).mul(a.dao()));
    			else if(cmp(A,zero)!=0) res.x=zero.sub(B.mul(res.y).add(C).mul(A.dao()));
    		return res;
    	}
    	boolean on(Point p){
    		Point sp=s.to(p);
    		Point se=s.to(e);
    		if(cmp(sp.cross(se),zero)!=0)
    			return false;
    		if(cmp(sp.x,zero)*cmp(se.x,zero)<0)
    			return false;
    		if(cmp(sp.y,zero)*cmp(se.y,zero)<0)
    			return false;
    		if(p.equals(e)||p.equals(s)) return false;
    		if(cmp(sp.x.abs().add(sp.y.abs()),se.x.abs().add(se.y.abs()))<0)
    			return true;
    		return false;
    	}
    }
}
2868868
74904ms