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
",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*log2(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
", solve(1, n) / 2);
}
return 0;
}