#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct Line
{
double x1,y1,x2,y2;
}a[400];
bool solve(Line a,Line b)
{
if(((a.x1 - b.x1) * (a.y2 - b.y1) - (a.x2 - b.x1) * (a.y1 - b.y1)) * ((a.x1 - b.x2) * (a.y2 - b.y2) - (a.x2 - b.x2) * (a.y1 - b.y2)) > 0)
return false;
if(((b.x1 - a.x1) * (b.y2 - a.y1) - (b.x2 - a.x1) * (b.y1 - a.y1)) * ((b.x1 - a.x2) * (b.y2 - a.y2) - (b.x2 - a.x2) * (b.y1 - a.y2)) > 0)
return false;
return true;
}
double xxx[400] = {0},yyy[400] = {0},x,y;
void GeneralEquation(Line a,double &A,double &B,double &C)
{
A = a.y2 - a.y1;
B = a.x1 - a.x2;
C = a.x2 * a.y1 - a.x1 * a.y2;
}
void GetIntersectPointofLines(Line a,Line b)
{
double A1,B1,C1;
GeneralEquation((Line){a.x1,a.y1,a.x2,a.y2},A1,B1,C1);
double A2, B2, C2;
GeneralEquation((Line){b.x1,b.y1,b.x2,b.y2},A2,B2,C2);
double m = A1 * B2 - A2 * B1;
x = (C2 * B1 - C1 * B2) / m;
y = (C1 * A2 - C2 * A1) / m;
}
int main()
{
freopen("sacrifice1.in","r",stdin);
freopen("sacrifice1.out","w",stdout);
//std::ios::sync_with_stdio(false);
int n;
int k;
cin >> k;
for(int s = 1;s <= k;s++)
{
cin >> n;
int sum = 0;
for(int i = 1; i <= n; i++)
scanf("%lf %lf %lf %lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
if(solve(a[i],a[j]))
sum++;
GetIntersectPointofLines(a[i],a[j]);
xxx[i] = x,yyy[i] = y;
}
}
cout << sum << endl;
for(int i = 1;i <= sum;i++)
printf("%.2f %.2f\n",xxx[i],yyy[i]);
}
return 0;
}
这是一个这样的问题:
有n条线段,你知道他们开头和结尾的坐标,现在求他们有几个交点,并输出他们的坐标