计算几何

　　poj 1269 : 求直线交点

　　这道题是给两条直线（输入直线上的两个点），然后问你两条直线是相交、重合还是平行。

　　很简单一道题。不过用g++测试的话double要用%f输出。不知道为什么。

　　（求交点的模板感觉很科学）

#include <cstdio>
#include <iostream>
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FE(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define zero(x) ((x>=0?x:-x)<1e-10)
#define debug(x) cout<<#x<<" = "<<x<<endl
using namespace std;

struct pot{
    double x,y;
    pot() { x=0; y=0; }
    pot(double _x, double _y):x(_x),y(_y){};
};
double cross(pot a,pot b) { return a.x*b.y-a.y*b.x; }
pot to_v(pot a,pot b) { pot c=pot(b.x-a.x,b.y-a.y); return c; }
pot intersection_line(pot u1,pot u2,pot v1,pot v2)
{
    pot ret = u1;
    double t = ((u1.x-v1.x)*(v1.y-v2.y) - (u1.y-v1.y)*(v1.x-v2.x))
             / ((u1.x-u2.x)*(v1.y-v2.y) - (u1.y-u2.y)*(v1.x-v2.x));
    ret.x += (u2.x-u1.x) * t;
    ret.y += (u2.y-u1.y) * t;
    return ret;
}

pot a[5];
int main()
{
    puts("INTERSECTING LINES OUTPUT");
    int n; scanf("%d",&n);
    for (pot ans;n--;)
    {
        FOR (i,1,4) scanf("%lf%lf",&a[i].x,&a[i].y);
        if (zero(cross(to_v(a[1],a[2]),to_v(a[3],a[4]))))
            if (zero(cross(to_v(a[1],a[2]),to_v(a[1],a[3])))) puts("LINE");
            else puts("NONE");
        else ans=intersection_line(a[1],a[2],a[3],a[4]),printf("POINT %.2f %.2f\n",ans.x,ans.y);
    }
    puts("END OF OUTPUT");
    return 0;
}
/*pot intersection_line(pot u1,pot u2,pot v1,pot v2)
{
    pot ret;
    double a1=u1.y-u2.y,b1=u2.x-u1.x,c1=u1.y*(u1.x-u2.x)-u1.x*(u1.y-u2.y);
    double a2=v1.y-v2.y,b2=v2.x-v1.x,c2=v1.y*(v1.x-v2.x)-v1.x*(v1.y-v2.y);
    ret.y=(a1*c2-a2*c1)/(a2*b1-a1*b2);
    ret.x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
    return ret;
}*/

//

　　

　　zoj 2107: 求最近点对

　　感觉好好写...而且我的算法虽然是O(n*log²(n))的，但是run出来还是很快。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define ABS(a) ((a)<0?-(a):(a))
#define DIS(a, b) sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y))
using namespace std;
const int maxn = 100001;

struct pot{
	double x, y;
	bool operator< (const pot &a) const { return x!=a.x ? x<a.x : y<a.y; }
};
bool cmp(pot a, pot b) { return a.y!=b.y ? a.y<b.y : a.x<b.x; }

int n;
pot wu[maxn];
pot dl[maxn];
double solve(int l, int r)
{
	if (l == r) return 1e308;
	if (l + 1 == r) return DIS(wu[l], wu[r]);
	int mid = l + r >> 1;
	double ret = min(solve(l, mid), solve(mid + 1, r));
	double MID = (wu[mid].x + wu[mid + 1].x) / 2;
	int dct = 0;
	for (int i = l; i <= r; i++)
		if (fabs(wu[i].x - MID) <= ret) dl[++dct] = wu[i];
	sort(dl + 1, dl + 1 + dct, cmp);
	for (int i = 2; i <= dct; i++)
		for (int j = max(1, i - 7); j < i; j++)
			ret = min(ret, DIS(dl[i], dl[j]));
	return ret;
}
int main()
{
	for (; scanf("%d", &n) != EOF; )
	{
		if (n == 0) break;
		for (int i = 1; i <= n; i++)
			scanf("%lf%lf", &wu[i].x, &wu[i].y);
		sort(wu + 1, wu + 1 + n);
		printf("%.2f\n", solve(1, n) / 2);
	}
	return 0;
}