多边形的公共部分
分析：
求多边形面积交模板题
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
Point p1[N], p2[N];
int n1, n2;
int idx = 1;
int dcmp(double x)
{
if (x > EPS)
return 1;
return x < -EPS ? -1 : 0;
}
struct Point
{
double x, y;
};
double cross(Point a, Point b, Point c) /// 叉积
{
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
Point intersection(Point a, Point b, Point c, Point d)
{
Point p = a;
double t = ((a.x - c.x) * (c.y - d.y) - (a.y - c.y) * (c.x - d.x)) / ((a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x));
p.x += (b.x - a.x) * t;
p.y += (b.y - a.y) * t;
return p;
}
// 计算多边形面积
double PolygonArea(Point p[], int n)
{
if (n < 3)
return 0.0;
double s = p[0].y * (p[n - 1].x - p[1].x);
p[n] = p[0];
for (int i = 1; i < n; ++i)
s += p[i].y * (p[i - 1].x - p[i + 1].x);
return fabs(s * 0.5);
}
double CPIA(Point a[], Point b[], int na, int nb) // ConvexPolygonIntersectArea
{
Point p[20], tmp[20];
int tn, sflag, eflag;
a[na] = a[0], b[nb] = b[0];
memcpy(p, b, sizeof(Point) * (nb + 1));
for (int i = 0; i < na && nb > 2; i++)
{
sflag = dcmp(cross(a[i + 1], p[0], a[i]));
for (int j = tn = 0; j < nb; j++, sflag = eflag)
{
if (sflag >= 0)
tmp[tn++] = p[j];
eflag = dcmp(cross(a[i + 1], p[j + 1], a[i]));
if ((sflag ^ eflag) == -2)
tmp[tn++] = intersection(a[i], a[i + 1], p[j], p[j + 1]); /// 求交点
}
memcpy(p, tmp, sizeof(Point) * tn);
nb = tn, p[nb] = p[0];
}
if (nb < 3)
return 0.0;
return PolygonArea(p, nb);
}
double SPIA(Point a[], Point b[], int na, int nb) /// SimplePolygonIntersectArea 调用此函数
{
int i, j;
Point t1[4], t2[4];
double res = 0, num1, num2;
a[na] = t1[0] = a[0], b[nb] = t2[0] = b[0];
for (i = 2; i < na; i++)
{
t1[1] = a[i - 1], t1[2] = a[i];
num1 = dcmp(cross(t1[1], t1[2], t1[0]));
if (num1 < 0)
swap(t1[1], t1[2]);
for (j = 2; j < nb; j++)
{
t2[1] = b[j - 1], t2[2] = b[j];
num2 = dcmp(cross(t2[1], t2[2], t2[0]));
if (num2 < 0)
swap(t2[1], t2[2]);
res += CPIA(t1, t2, 3, 3) * num1 * num2;
}
}
return PolygonArea(a, na) + PolygonArea(b, nb) - res; // res为两凸多边形的交的面积
}
int T;
void solve()
{
while (~scanf("%d", &n1))
{
for (int i = 0; i < n1; i++)
{
scanf("%lf%lf", &p1[i].x, &p1[i].y);
}
scanf("%d", &n2);
for (int i = 0; i < n2; i++)
{
scanf("%lf%lf", &p2[i].x, &p2[i].y);
}
double Area = SPIA(p1, p2, n1, n2);
// Area=PolygonArea(p1,n1)+PolygonArea(p2,n2)-Area;
double s1 = PolygonArea(p1, n1), s2 = PolygonArea(p2, n2);
printf("Case %d: ", idx);
idx++;
if (s1 + s2 - Area > 0)
puts("Yes");
else
puts("No");
}
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
简单的图论问题?
分析：
BFS1正常求值， BFS2记录上一次方向在求值
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
typedef unordered_map<int, int> Ump;
int T;
int n, m, r1, c1, r2, c2;
int g[N][N];
int idx = 1;
int d[N][N];
bool st[N][N], vis[N][N][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct Node
{
int x, y, dir;
int step;
};
bool operator<(Node a, Node b)
{
return a.step > b.step;
}
bool check(int x, int y)
{
if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != -1 && !st[x][y])
return true;
return false;
}
int bfs1(int stx, int sty)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
d[i][j] = 0x3f3f3f3f, st[i][j] = false;
d[stx][sty] = g[stx][sty];
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
heap.push({g[stx][sty], {stx, sty}});
while (heap.size())
{
auto t = heap.top();
heap.pop();
for (int i = 0; i < 4; i++)
{
int xx = t.second.first + dx[i], yy = t.second.second + dy[i];
if (check(xx, yy))
{
d[xx][yy] = min(d[xx][yy], d[t.second.first][t.second.second] + g[xx][yy]);
heap.push({d[xx][yy], {xx, yy}});
st[xx][yy] = true;
if (xx == r2 && yy == c2)
return d[xx][yy];
}
}
}
return -1;
}
int bfs2(int stx, int sty)
{
if (c1 == c2 && r1 == r2)
return 0;
priority_queue<struct Node> que;
memset(vis, 0, sizeof(vis));
Node no, next, now;
no.x = r1;
no.y = c1;
no.step = g[r1][c1];
no.dir = -1;
que.push(no);
vis[r1][c1][0] = vis[r1][c1][1] = vis[r1][c1][2] = vis[r1][c1][3] = 1;
while (!que.empty())
{
now = que.top();
que.pop();
if (now.x == r2 && now.y == c2)
return now.step;
for (int i = 0; i < 4; i++)
{
next.x = now.x + dx[i];
next.y = now.y + dy[i];
if (now.dir == i)
continue;
if (next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= m && g[next.x][next.y] != -1 && !vis[next.x][next.y][i])
{
vis[next.x][next.y][i] = 1;
next.step = now.step + g[next.x][next.y];
next.dir = i;
que.push(next);
}
}
}
return -1;
}
void solve()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char ch[5];
cin >> ch;
if (ch[0] == '*')
g[i][j] = -1;
else
g[i][j] = atoi(ch);
}
}
cout << "Case " << idx++ << ": ";
cout << bfs1(r1, c1) << " " << bfs2(r1, c1) << endl;
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (cin >> n >> m >> r1 >> c1 >> r2 >> c2)
solve();
return 0;
}