B. 辉哥的像素画

思路

问题可以转化为，给定一个三角形，判断某个点是否在三角形内。然后遍历每个点就好

有三种方法：

  1. 向量叉积法：
    • 主要利用向量叉积的方向性，如果一个点PP在三角形ABCABC内部，那一定满足：
    • AB⃗∗AP⃗\vec{AB} * \vec{AP}、BC⃗∗BP⃗\vec{BC} * \vec{BP}、CA⃗∗CP⃗\vec{CA}*\vec{CP}三个向量同向（其中∗*指向量的叉积，可能有多种写法，注意方向性，自己比划一下）
  2. 直线公式法：
    • 叉积没学好的同学可以用直线公式法，这也是比赛中很多同学提交并且WA掉的方法，主要需要注意因为斜率可能不存在，而且可能产生浮点数导致精度爆炸，所以建议使用直线一般式，同时把分母约掉
    • 具体的方法就是判断P、A在直线BC同侧，P、B在直线AC同侧，P、C在直线AB同侧，则说明PP在三角形ABCABC内，只要有一个在异侧，说明在三角形外
  3. 面积法：
    • 如果SABC=SPAB+SPAC+SPBCS_{ABC}=S_{PAB} + S_{PAC} + S_{PBC}，则说明PP点在三角形ABCABC内部
    • 需要注意的是如果使用面积可能会因为浮点数的精度问题导致WA，尤其是使用海伦公式计算面积要经过两次开根号；所以建议使用坐标计算面积（可以使用叉积算面积或者直接推导面积公式），由于坐标点都是整数，使用坐标计算面积时，除了最后有一个除以2不存在除法或根号等产生浮点数的运算，所以可以通过计算面积的2倍来完全避开浮点精度产生的问题，不使用二倍面积去判断也可以通过，稍微控制下精度就好。

std

std1.cpp(向量叉乘法)

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long llong;
const int MOD = 1e9 + 7;
const int N = 1e3 + 5;

struct Point {
    typedef Point Vector;
    int x, y, z;
    Point(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) { }
    Vector operator - (const Point& b) const {
        return Point(b.x - x, b.y - y, b.z - z);
    }
    Vector operator * (const Point& b) const {  // 向量叉乘
        return Point(y * b.z - b.y * z, z * b.x - x * b.z, x * b.y - y * b.x);
    }
};
typedef Point Vector;

int n, k;
Point p[5];
Vector v[5];
int s[5];

bool judge(const Point& pp) {
    for (int i = 0; i < 3; i++) {
        s[i] = (v[i] * (pp - p[i])).z;
    }
    return (s[0] >= 0 && s[1] >= 0 && s[2] >= 0) || (s[0] <= 0 && s[1] <= 0 && s[2] <= 0);
}

int main() {
    int n;  cin >> n;
    for (int i = 0; i < 3; i++) {
        cin >> p[i].x >> p[i].y;
    }
    p[3] = p[0];    // 这里不写也可以，只是后面p[i+1]要写成p[(i+1)%3]
    for (int i = 0; i < 3; i++) {
        v[i] = p[i + 1] - p[i];
    }
    for (int y = n - 1; y >= 0; y--) {
        for (int x = 0; x < n; x++) {
            if (judge(Point(x, y))) {
                cout << "*";
            } else {
                cout << ".";
            }
        }   cout << endl;
    }
    return 0;
}

std2.cpp(直线公式法)

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long llong;
const int MOD = 1e9 + 7;
const int N = 1e3 + 5;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) { }
};

struct Lines {
    int a, b, c;    // 直线一般式的三个参数ABC, Ax+By+C=0
    Lines(int a = 0, int b = 0, int c = 0) : a(a), b(b), c(c) { }
    Lines(const Point& p1, const Point& p2) {   // 通过p1和p2两点的直线方程，手算很容易算出来
        a = p1.y - p2.y;
        b = p2.x - p1.x;
        c = p1.x * p2.y - p1.y * p2.x;
    }
    int side(const Point& p) const {    
        int t = a * p.x + b * p.y + c;
        return t > 0 ? 1 : (t == 0 ? 0 : -1);
        // 这里返回符号而不是原值，避免后面乘法爆int
    }
};

int n, k;
Point p[5];
Lines l[5];

bool judge(const Point& pp) {
    if (l[0].side(pp) * l[0].side(p[2]) < 0)  return false;
    if (l[1].side(pp) * l[1].side(p[0]) < 0)  return false;
    if (l[2].side(pp) * l[2].side(p[1]) < 0)  return false;
    return true;
}

int main() {
    int n;  cin >> n;
    for (int i = 0; i < 3; i++) {
        cin >> p[i].x >> p[i].y;
    }
    p[3] = p[0];
    for (int i = 0; i < 3; i++) {
        l[i] = Lines(p[i], p[i + 1]);
    }
    for (int y = n - 1; y >= 0; y--) {
        for (int x = 0; x < n; x++) {
            if (judge(Point(x, y))) {
                cout << "*";
            } else {
                cout << ".";
            }
        }   cout << endl;
    }
    return 0;
}

std3.cpp(面积法)

#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
typedef long long llong;
const int MOD = 1e9 + 7;
const int N = 1e3 + 5;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) { }
};

int n, k;
Point p[5];

int getTwiceArea(Point a, Point b, Point c) {   // 二倍的面积，可以通过坐标直接算，也可以用叉积算
    return abs((a.x - b.x) * (a.y - c.y) - (a.y - b.y) * (a.x - c.x));
}

bool judge(const Point& pp) {
    int ans1 = getTwiceArea(p[0], p[1], p[2]);
    int ans2 = 0;
    for (int i = 0; i < 3; i++) {
        ans2 += getTwiceArea(pp, p[i], p[i + 1]);
    }
    return ans1 == ans2;
}

int main() {
    int n;  cin >> n;
    for (int i = 0; i < 3; i++) {
        cin >> p[i].x >> p[i].y;
    }
    p[3] = p[0];
    for (int y = n - 1; y >= 0; y--) {
        for (int x = 0; x < n; x++) {
            if (judge(Point(x, y))) {
                cout << "*";
            } else {
                cout << ".";
            }
        }   cout << endl;
    }
    return 0;
}