思路：转换成n条三维空间的直线，求最大的集合使得两两有交点。
有两种情况:第一种是以某2条直线为平面，这时候只要统计这个平面上有几条斜率不同的直线就可以了
还有一种是全部交于同一点，这个也只要判断就可以了。
然后我并不能改出来，wa了好多个点
WA的程序:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define dou long double
const dou eps=1e-;
int n;
struct Point{
dou x,y,z;
Point(){}
Point(dou x0,dou y0,dou z0):x(x0),y(y0),z(z0){}
};
struct Line{
Point s,e,p;
int id;
Line(){}
Line(Point s0,Point e0):s(s0),e(e0){}
}l[];
int tmp[];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
bool cmp(Line l1,Line l2){
Point p1=l1.p,p2=l2.p;
if (fabs(p1.x-p2.x)<eps&&fabs(p1.y-p2.y)<eps) return p1.z<p2.z;
else
if (fabs(p1.x-p2.x)<eps) return p1.y<p2.y;
return p1.x<p2.x;
}
bool operator ==(Point p1,Point p2){
return fabs(p1.x-p2.x)<=eps&&fabs(p1.y-p2.y)<=eps&&fabs(p1.z-p2.z)<=eps;
}
bool operator !=(Point p1,Point p2){
if (p1==p2) return ;
else return ;
}
double operator /(Point p1,Point p2){
return p1.x*p2.x+p1.y*p2.y+p1.z*p2.z;
}
Point operator -(Point p1,Point p2){
return Point(p1.x-p2.x,p1.y-p2.y,p1.z-p2.z);
}
Point operator *(Point p1,Point p2){
return Point(p1.y*p2.z-p1.z*p2.y,p1.z*p2.x-p1.x*p2.z,p1.x*p2.y-p1.y*p2.x);
}
Point operator /(Point p1,dou x){
return Point(p1.x/x,p1.y/x,p1.z/x);
}
dou sqr(dou x){
return x*x;
}
dou dist(Point p){
return sqrt(sqr(p.x)+sqr(p.y)+sqr(p.z));
}
dou dist(Point p1,Point p2){
return dist(p1-p2);
}
bool zero(dou x){
if (fabs(x)<eps) return ;
return ;
}
bool zero(Point p){
return zero(p.x)&&zero(p.y)&&zero(p.z);
}
bool LineIntersect(Line p1, Line p2){
dou x1=p1.s.x,x2=p1.e.x,x3=p2.s.x,x4=p2.e.x;
dou y1=p1.s.y,y2=p1.e.y,y3=p2.s.y,y4=p2.e.y;
dou z1=p1.s.z,z2=p1.e.z,z3=p2.s.z,z4=p2.e.z;
dou x12=(x1-x2),x13=(x1-x3),x34=(x3-x4);
dou y12=(y1-y2),y13=(y1-y3),y34=(y3-y4);
dou z12=(z1-z2);
dou t=(y34*x12-x34*y12);
if (fabs(t)<eps) return ;
return ;
}
Point inter(Line p1,Line p2){
dou x1=p1.s.x,x2=p1.e.x,x3=p2.s.x,x4=p2.e.x;
dou y1=p1.s.y,y2=p1.e.y,y3=p2.s.y,y4=p2.e.y;
dou z1=p1.s.z,z2=p1.e.z,z3=p2.s.z,z4=p2.e.z;
dou x12=(x1-x2),x13=(x1-x3),x34=(x3-x4);
dou y12=(y1-y2),y13=(y1-y3),y34=(y3-y4);
dou z12=(z1-z2);
dou t=(y13*x34-y34*x13)/(y34*x12-x34*y12);
dou x=x1+x12*((y13*x34-y34*x13)/(y34*x12-x34*y12));
dou y=y1+y12*t,z=z1+z12*t;
return Point(x,y,z);
}
void solve(){
int ans=;
for (int i=;i<=n;i++){
Point p=l[i].e-l[i].s;
dou len=dist(p);
p=p/len;
l[i].p=p;
}
std::sort(l+,l++n,cmp);
int id=;
l[].id=;
for (int i=;i<=n;i++)
if (l[i].p!=l[i-].p)
l[i].id=++id;
else
l[i].id=id;
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++)
if (LineIntersect(l[i],l[j])){
Point p=inter(l[i],l[j]);
Point e1=l[i].e-l[i].s,e2=l[j].e-l[j].s;
dou len1=dist(e1),len2=dist(e2);
e1=e1/len1;e2=e2/len2;
dou x1=e1.x,x2=e2.x,y1=e1.y,y2=e2.y,z1=e1.z,z2=e2.z;
dou x=;
dou y=(x2*z1-x1*z2)/(y1*z2-z1*y2);
dou z=(-x1*x-y1*y)/z1;
Point e=Point(x,y,z);
for (int k=;k<=n;k++) tmp[k]=;
tmp[l[i].id]=;tmp[l[j].id]=;
for (int k=;k<=n;k++)
if (k!=i&&k!=j)
if (fabs((l[k].e-l[k].s)/e)<eps&&LineIntersect(l[i],l[k])) tmp[l[k].id]=;
int cnt=;
for (int k=;k<=n;k++) if (tmp[k]) cnt++;
ans=std::max(ans,cnt);
cnt=;
for (int k=;k<=n;k++)
if (k!=i&&k!=j)
if ((inter(l[k],l[i])==p)) cnt++;
ans=std::max(ans,cnt);
}
printf("%d\n",ans);
}
int main(){
freopen("spider.txt","r",stdin);
n=read();
for (int i=;i<=n;i++){
int kx=read(),bx=read(),ky=read(),by=read();
Point p1,p2;
p1.x=-;p1.y=-kx+bx;p1.z=-ky+by;
p2.x=;p2.y=kx+bx;p2.z=ky+by;
l[i]=Line(p1,p2);
}
solve();
}
只好改成std的写法了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define sz 1020000
#define ll long long int
using namespace std;
int n,ans=;
ll kx[sz],ky[sz],bx[sz],by[sz];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
ll gcd(ll a,ll b){
if (b==) return a;
else return gcd(b,a%b);
}
bool ok(ll i,ll j,ll &X,ll &Y,ll &T,ll &T2){
if (kx[i] == kx[j]){
if (ky[i] == ky[j]) return ;
T = by[i] - by[j]; T2 = ky[j] - ky[i];
} else{
T = bx[i] - bx[j]; T2 = kx[j] - kx[i];
}
if (kx[i] * T + bx[i] * T2 == kx[j] * T + bx[j] * T2 &&
ky[i] * T + by[i] * T2 == ky[j] * T + by[j] * T2){
X = kx[i] * T + bx[i] * T2;
Y = ky[i] * T + by[i] * T2;
ll g = gcd(gcd(X, Y), gcd(T, T2));
X /= g; Y /= g; T /= g; T2 /= g; return ;
} else return ;
}
void plane(ll i,ll j,ll &A,ll &B,ll &C,ll &D){
if (bx[i]-bx[j]==&&by[i]-by[j]==){
A=ky[i]-ky[j],B=kx[i]-kx[j];
}else{
A=by[i]-by[j],B=bx[i]-bx[j];
}
C=A*kx[i]+B*ky[i];
D=A*bx[i]+B*by[i];
ll g=gcd(gcd(A,B),gcd(C,D));
A/=g;B/=g;C/=g;D/=g;
}
class Hash{
public:
ll F(ll a, ll b, ll c, ll d){
ll s = (a * + b * + c * + d * ) % ;
if (s < ) s = -s;
return s;
}
ll node[], next[sz], A[sz], B[sz], C[sz], D[sz], pass[sz];
ll e;
void ins(ll a,ll b,ll c,ll d){
ll s=F(a,b,c,d);
e++;
next[e]=node[s];node[s]=e;
A[e]=a;B[e]=b;C[e]=c;D[e]=d;
}
bool find(ll a,ll b,ll c,ll d){
ll s=F(a,b,c,d),j;
for (j=node[s];j;j=next[j]){
if (A[j]==a&&B[j]==b&&C[j]==c&&D[j]==d)
return ;
}
return ;
}
}Point,Plane,Slope;
int main(){
freopen("spider.txt","r",stdin);
ll A,B,C,D;
n=read();
for (int i=;i<=n;i++)
kx[i]=read(),bx[i]=read(),ky[i]=read(),by[i]=read();
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++)
if (ok((ll)i,(ll)j,A,B,C,D)){
if (!Point.find(A,B,C,D)) Point.ins(A,B,C,D);
plane(i,j,A,B,C,D);
if (!Plane.find(A,B,C,D)) Plane.ins(A,B,C,D);
}
for (ll i=;i<=Point.e;i++){
for (ll a=;a<=n;a++){
if (kx[a]*Point.C[i]+bx[a]*Point.D[i]==Point.A[i])
if (ky[a]*Point.C[i]+by[a]*Point.D[i]==Point.B[i])
Point.pass[i]++;
}
}
for (ll i=;i<=Plane.e;i++){
for (ll a=;a<=n;a++){
if (kx[a] * Plane.A[i] + ky[a] * Plane.B[i] == Plane.C[i])
if (bx[a] * Plane.A[i] + by[a] * Plane.B[i] == Plane.D[i])
if (!Slope.find(kx[a],ky[a],i,)){
Plane.pass[i]++;
Slope.ins(kx[a],ky[a],i,);
}
}
}
for (int i=;i<=Point.e;i++)
if (Point.pass[i]>ans) ans=Point.pass[i];
for (int i=;i<=Plane.e;i++)
if (Plane.pass[i]>ans) ans=Plane.pass[i];
printf("%d\n",ans);
}
