12.5 เรขาคณิตบนพิกัด

โจทย์ที่ให้ตำแหน่งเป็นพิกัด (x, y) เช่น บ้านของนักเรียน ร้านค้าบนแผนที่ หรือหมุดเขตที่ดิน มักถามระยะห่าง ใครอยู่ใกล้สุด หรือพื้นที่ของรูปที่ล้อมด้วยหมุด หน้านี้ใช้สูตรจากวิชาคณิตศาสตร์ แต่เขียนให้คำนวณด้วยจำนวนเต็มให้มากที่สุด เพราะทศนิยมคลาดได้ตามที่เห็นในหน้า 1.4 และในโจทย์เรขาคณิต ค่าที่คลาดนิดเดียวทำให้ตอบผิดทั้งข้อได้

ระยะห่างระหว่างสองจุด

จุด (x1, y1) กับ (x2, y2) ห่างกันในแนวนอน dx = x2 - x1 และแนวตั้ง dy = y2 - y1 ตามทฤษฎีบทพีทาโกรัส ระยะห่างคือ √(dx² + dy²) ซึ่งหน้า 8.5 เขียนด้วย sqrt จาก math.h ไปแล้ว ต่างกันตรงที่หน้านั้นเก็บพิกัดเป็น double ส่วนหน้านี้เก็บเป็นจำนวนเต็ม แล้วแปลงเป็นทศนิยมตอนถอดรากเท่านั้น

#include <stdio.h>
#include <math.h>

int main()
{
    long long x1, y1, x2, y2;
    scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
    long long dx = x2 - x1;
    long long dy = y2 - y1;
    long long squared = dx * dx + dy * dy;
    printf("squared = %lld\n", squared);
    printf("distance = %.2f\n", sqrt(squared));
    return 0;
}

-2 -1 3 2

squared = 34
distance = 5.83

dx = 5 และ dy = 3 ระยะห่างคือ √34 ไม่เป็นจำนวนเต็ม จึงต้องพิมพ์เป็นทศนิยม แต่ squared คำนวณเป็นจำนวนเต็มจนวินาทีสุดท้าย แปลงเป็น double ตอนส่งให้ sqrt เท่านั้น ถ้าพิกัดใหญ่ถึง 10⁹ ค่า dx ใหญ่ถึง 2 × 10⁹ และ dx × dx ถึง 4 × 10¹⁸ จึงต้องเป็น long long ทุกตัว

เทียบระยะไม่ต้องถอดราก

หน้า 8.5 บอกไว้แล้วว่าถ้าโจทย์ถามแค่ว่าใครอยู่ใกล้กว่า ให้เทียบ dx² + dy² ตรงๆ ไม่ต้องใช้ sqrt ตัวอย่างนี้ทำให้ดูเต็มโปรแกรม โรงเรียนอยู่ที่ (0, 0) หาว่าบ้านของนักเรียนคนไหนใกล้โรงเรียนที่สุด

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    long long best = -1;
    int best_index = 0;
    for (int i = 1; i <= n; i++) {
        long long x, y;
        scanf("%lld %lld", &x, &y);
        long long squared = x * x + y * y;
        if (best == -1 || squared < best) {
            best = squared;
            best_index = i;
        }
    }
    printf("nearest = %d\n", best_index);
    printf("squared distance = %lld\n", best);
    return 0;
}

4
5 5
-6 2
1 -7
3 -6

nearest = 2
squared distance = 40

กำลังสองของระยะคือ 50 40 50 และ 45 คนที่ 2 ใกล้สุด ส่วนคนที่ 1 กับคนที่ 3 ห่างเท่ากันพอดี ซึ่งเทียบด้วยจำนวนเต็มรู้ได้แน่นอน ถ้าเทียบด้วยทศนิยมจาก sqrt อาจเจอค่าที่ควรเท่ากันแต่คลาดกันในหลักท้ายๆ

ถ้าโจทย์เป็นการเดินบนตารางที่เดินได้แค่ขึ้นลงซ้ายขวา ระยะที่เดินจริงคือ |dx| + |dy| เรียกว่าระยะแมนฮัตตัน (Manhattan distance) ตามถนนที่ตัดกันเป็นตารางในเมืองนั้น คำนวณด้วยจำนวนเต็มล้วน ค่าสัมบูรณ์ทำได้ด้วย if แบบในโปรแกรมข้างล่าง

พื้นที่สามเหลี่ยมจากพิกัด

สูตรครึ่งหนึ่งของฐานคูณสูงต้องรู้ความสูง ซึ่งหาจากพิกัดยาก มีสูตรที่ใช้พิกัดสามจุดตรงๆ และมีแค่การบวก ลบ คูณ

2 × พื้นที่ = | x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2) |

ค่าในเครื่องหมายค่าสัมบูรณ์เป็นจำนวนเต็มเสมอเมื่อพิกัดเป็นจำนวนเต็ม พื้นที่จึงเป็นจำนวนเต็มหรือลงท้ายด้วย .5 เท่านั้น เก็บค่าสองเท่าของพื้นที่ไว้เป็นจำนวนเต็มแล้วพิมพ์เองโดยไม่ต้องใช้ double เลย

#include <stdio.h>

int main()
{
    long long x1, y1, x2, y2, x3, y3;
    scanf("%lld %lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &x3, &y3);
    long long twice = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
    if (twice < 0) { // (1)!
        twice = -twice;
    }
    if (twice == 0) { // (2)!
        printf("on one line\n");
    } else if (twice % 2 == 0) {
        printf("area = %lld.0\n", twice / 2);
    } else {
        printf("area = %lld.5\n", twice / 2);
    }
    return 0;
}

1. ค่าจากสูตรติดลบเมื่อไล่สามจุดตามเข็มนาฬิกา และเป็นบวกเมื่อไล่ทวนเข็มนาฬิกา เครื่องหมายนี้ใช้บอกทิศได้ด้วย แต่พื้นที่ต้องเป็นบวก จึงกลับเครื่องหมายก่อน และต้องทำก่อนดู % 2 เพราะเศษของเลขติดลบเป็น -1 ตามหน้า 12.1
2. สามจุดอยู่บนเส้นตรงเดียวกันพอดีเมื่อค่านี้เป็น 0 เทียบกับ 0 แบบจำนวนเต็มได้แน่นอน

1 1 5 1 1 4

area = 6.0

สามเหลี่ยมมุมฉากฐาน 4 สูง 3 พื้นที่ 6 ตรงกับสูตรครึ่งฐานคูณสูง ป้อน 0 0 3 1 1 2 ได้ area = 2.5 และป้อน 0 0 1 1 3 3 ได้ on one line

พื้นที่รูปหลายเหลี่ยม

สูตรเดียวกันขยายไปใช้กับรูปหลายเหลี่ยมกี่เหลี่ยมก็ได้ ถ้ารู้พิกัดของทุกมุมเรียงตามขอบรูป จะเรียงตามหรือทวนเข็มนาฬิกาก็ได้ เรียกว่าสูตรเชือกผูกรองเท้า (shoelace formula) เพราะถ้าเขียนพิกัดเป็นสองคอลัมน์แล้วลากเส้นคูณไขว้ จะดูเหมือนเชือกผูกรองเท้า

2 × พื้นที่ = | ผลรวมของ (x[i] × y[i+1] - x[i+1] × y[i]) ทุก i |
              โดยมุมถัดจากมุมสุดท้ายคือมุมแรก

ที่ดินรูปตัว L มีหมุด 6 หมุด

#include <stdio.h>

long long x[100000], y[100000];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &x[i], &y[i]);
    }
    long long twice = 0;
    for (int i = 0; i < n; i++) {
        int next = (i + 1) % n;
        twice += x[i] * y[next] - x[next] * y[i];
    }
    if (twice < 0) {
        twice = -twice;
    }
    printf("%lld", twice / 2);
    if (twice % 2 == 1) {
        printf(".5\n");
    } else {
        printf(".0\n");
    }
    return 0;
}

6
0 0
4 0
4 2
2 2
2 5
0 5

14.0

ตรวจด้วยมือได้ ตัว L นี้คือสี่เหลี่ยม 4 × 2 ต่อกับสี่เหลี่ยม 2 × 3 รวม 8 + 6 = 14 (i + 1) % n ทำให้มุมถัดจากมุมสุดท้ายวนกลับไปมุมที่ 0 แบบเดียวกับการวนรอบในหน้า 12.1 ถ้าพิกัดไม่เรียงตามขอบรูป เช่น สลับลำดับหมุดสองตัว สูตรจะได้พื้นที่ของรูปที่เส้นขอบตัดกันเอง ซึ่งไม่ใช่ที่ดินแปลงนี้

ลองทำให้พัง

แบบที่ 1 หาพื้นที่ด้วยทศนิยม

สูตรของเฮรอนหาพื้นที่จากความยาวด้านสามด้าน a b c ได้เป็น √(s(s - a)(s - b)(s - c)) เมื่อ s คือครึ่งหนึ่งของเส้นรอบรูป ความยาวด้านต้องหาด้วย sqrt จึงเป็นทศนิยมตั้งแต่ต้น ใช้ตรวจว่าสามจุดอยู่บนเส้นตรงเดียวกันไหม

#include <stdio.h>
#include <math.h>

int main()
{
    double x1, y1, x2, y2, x3, y3;
    scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
    double a = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    double b = sqrt((x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2));
    double c = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
    double s = (a + b + c) / 2;
    double area = sqrt(s * (s - a) * (s - b) * (s - c));
    printf("%.10f\n", area);
    if (area == 0) {
        printf("on one line\n");
    } else {
        printf("triangle\n");
    }
    return 0;
}

0 0 1 1 3 3

0.0000001228
triangle

(0, 0) (1, 1) (3, 3) อยู่บนเส้น y = x ทั้งสามจุด พื้นที่ต้องเป็น 0 แต่ √2 กับ 3√2 เก็บแบบลงตัวไม่ได้ ค่าที่คลาดนิดเดียวสะสมจนได้พื้นที่ไม่เป็นศูนย์ โปรแกรมจึงตอบว่าเป็นสามเหลี่ยม บางชุดพิกัดได้ 0 พอดี บางชุดไม่ได้ ทดสอบไม่กี่ชุดจึงอาจไม่เห็น โปรแกรม triangle ที่ใช้จำนวนเต็มตอบชุดนี้ถูก และถูกทุกชุด

แบบที่ 2 ใช้ int เก็บพิกัด

เปลี่ยนตัวแปรพิกัดในโปรแกรม triangle เป็น int คิดว่าเก็บผลใน long long แล้วก็พอ

#include <stdio.h>

int main()
{
    int x1, y1, x2, y2, x3, y3;
    scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3);
    long long twice = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
    if (twice < 0) {
        twice = -twice;
    }
    printf("twice area = %lld\n", twice);
    return 0;
}

0 0 100000 0 0 100000

twice area = 1410065408

ค่าที่ถูกคือ 100000 × 100000 = 10000000000 แต่ x2 * (y3 - y1) เป็น int คูณ int ล้นไปก่อนถึงกล่อง long long เป็นกับดักจากหน้า 1.3 อีกครั้ง โจทย์เรขาคณิตคูณพิกัดกันเกือบทุกบรรทัด ให้ประกาศพิกัดเป็น long long ตั้งแต่ต้น และเช็กขอบเขตด้วย พิกัดถึง 10⁹ ทำให้แต่ละพจน์ใหญ่ถึง 2 × 10¹⁸ ยังพอสำหรับสามเหลี่ยม แต่รูปหลายเหลี่ยมที่บวกพจน์เป็นแสนพจน์อาจเกิน long long โจทย์แบบนั้นจึงมักให้พิกัดเล็กกว่านี้

สรุป

• ระยะห่างคือ √(dx² + dy²) ใช้ sqrt จาก math.h เฉพาะตอนต้องพิมพ์ระยะจริง
• เทียบว่าใกล้หรือไกลกว่า ให้เทียบ dx² + dy² ซึ่งเป็นจำนวนเต็ม ไม่ต้องถอดราก
• สองเท่าของพื้นที่สามเหลี่ยมคือ |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)| เป็นจำนวนเต็มเสมอ เป็น 0 เมื่อสามจุดอยู่บนเส้นตรงเดียวกัน
• รูปหลายเหลี่ยมใช้สูตรเชือกผูกรองเท้า พิกัดต้องเรียงตามขอบรูป และวนมุมสุดท้ายกลับไปมุมแรกด้วย (i + 1) % n
• พิกัดเป็น long long เสมอ และทำงานกับสองเท่าของพื้นที่แบบจำนวนเต็ม แทนการใช้ double

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด