You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
69 lines
1.8 KiB
C++
69 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
typedef struct Point
|
|
{
|
|
double x, y;
|
|
|
|
double operator*(const Point &b)
|
|
{
|
|
return x * b.x + y * b.y;
|
|
}
|
|
double operator^(const Point &b)
|
|
{
|
|
return x * b.y - y * b.x;
|
|
}
|
|
} point, vec;
|
|
//vec operator-(const vec &lhs, const vec &rhs) { return {lhs.x - rhs.x, lhs.y - rhs.y}; }
|
|
point operator-(const point &lhs, const point &rhs) { return {lhs.x - rhs.x, lhs.y - rhs.y}; }
|
|
const double eps = 1e-6;
|
|
int sgn(double x)
|
|
{
|
|
|
|
if (x < -eps)
|
|
return -1;
|
|
if (x > eps)
|
|
return 1;
|
|
return 0;
|
|
}
|
|
point p[1010];
|
|
struct Edge
|
|
{
|
|
int f, t;
|
|
} e[2020];
|
|
bool SegmentCross(point a1, point a2, point b1, point b2)
|
|
{
|
|
double c1 = sgn((a2 - a1) ^ (b1 - a1));
|
|
double c2 = sgn((a2 - a1) ^ (b2 - a1));
|
|
double c3 = sgn((b2 - b1) ^ (a1 - b1));
|
|
double c4 = sgn((b2 - b1) ^ (a2 - b1));
|
|
//正规相交
|
|
if (c1 * c2 < 0 && c3 * c4 < 0)
|
|
return 1;
|
|
return 0;
|
|
return (c1 == 0 && sgn((a1 - b1) * (a2 - b1)) <= 0) ||
|
|
(c2 == 0 && sgn((a1 - b2) * (a2 - b2)) <= 0) ||
|
|
(c3 == 0 && sgn((b1 - a1) * (b2 - a1)) <= 0) ||
|
|
(c4 == 0 && sgn((b1 - a2) * (b2 - a2)) <= 0);
|
|
}
|
|
bool inters(const Edge &lhs, const Edge &rhs)
|
|
{
|
|
point p1 = p[lhs.f], p2 = p[lhs.t], p3 = p[rhs.f], p4 = p[rhs.t];
|
|
return SegmentCross(p1, p2, p3, p4);
|
|
//vec l1 = p2 - p1, l2 = p4 - p3;
|
|
}
|
|
int main()
|
|
{
|
|
int n, m;
|
|
scanf("%d%d", &n, &m);
|
|
for (int i = 0; i < m; i++)
|
|
scanf("%d%d", &e[i].f, &e[i].t);
|
|
for (int i = 0; i < n; i++)
|
|
scanf("%lf%lf", &p[i].x, &p[i].y);
|
|
int ans = 0;
|
|
for (int i = 0; i < m; i++)
|
|
for (int j = i + 1; j < m; j++)
|
|
if (inters(e[i], e[j]))
|
|
ans++;
|
|
printf("%d", ans);
|
|
return 0;
|
|
} |