কনটেন্টে যান

115 — Area of Triangle

এই note-এ cross product আমাদের নতুন এক উপহার দেবে — area। 114-এ দেখেছ এই গুণফল collinearity বলে; আজ দেখবে সেই একই গুণফলের মান হলো triangle-এর দ্বিগুণ ক্ষেত্রফল। আর integer-এ থাকার মন্ত্র মেনে আমরা যতক্ষণ পারি "doubled area"-তে থাকব — শুধু একদম শেষে 2 দিয়ে ভাগ। এটাই shoelace formula-র প্রথম ধাপ।

Problem link ও উৎস

  • Original source: Classic exercise (school triangle area, shoelace/determinant রূপে)
  • Platform: Classic exercise (polygon area সব geometry set-এ আছে)
  • Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
  • Difficulty: Easy
  • Pattern: shoelace
  • Basic idea inherited from: 114 — Slope and Collinearity (একই cross product রাশি, এবার মান = area)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তিনটা point দেওয়া — A, B, C — এরা একটা triangle-এর তিন কোণা। বলতে হবে এই triangle-এর ক্ষেত্রফল (area) কত।

দুটো রূপ দরকার হতে পারে:

  • doubled area — area-র দ্বিগুণ, যেটা সবসময় integer (যদি point-গুলো integer হয়), তুলনার জন্য আদর্শ
  • আসল area — সেই doubled area-কে 2 দিয়ে ভাগ, যেমন 6.0 বা 7.5

আর base × height-এর সেই পুরনো ঝামেলা (height বের করতে দূরত্ব, লম্ব...) — এসব ছাড়াই, শুধু coordinate থেকে সরাসরি।

Input ও output

উদাহরণ
A         B         C          2*area    area
---------------------------------------------------
(0,0)     (4,0)     (4,3)      12        6.0
(0,0)     (4,0)     (0,3)      12        6.0    (সমকোণী, ½*4*3 = 6)
(0,0)     (2,0)     (1,1)       2        1.0
(0,0)     (1,1)     (2,2)       0        0.0    (collinear → area 0!)
(0,0)     (4,0)     (2,3)      12        6.0    (CCW)
(0,0)     (2,3)     (4,0)     -12 -> 12   6.0   (CW: signed -12, abs নিলে 12)

খেয়াল করো: collinear তিন point দিলে area 0 (114-এর সাথে মিলে গেল); আর point-এর ক্রম উল্টে দিলে signed area-র চিহ্ন বদলায়, কিন্তু abs নিলে area একই থাকে।

চেনা উদাহরণে বোঝা

ভাবো একটা জমির তিন কোণায় তিনটা খুঁটি পোঁতা, আর তুমি জমিটার ক্ষেত্রফল মাপতে চাও — কিন্তু হাতে শুধু GPS coordinate, ফিতা নেই।

পুরনো উপায়: এক বাহুকে base ধরে, লম্ব দূরত্ব (height) মেপে, ½ × base × height। কিন্তু height মাপা ঝামেলা।

Shoelace বলে: শুধু তিন কোণার coordinate দাও, আমি আড়াআড়ি গুণ করে সরাসরি area বলে দিচ্ছি — কোনো height-টিকটিকি লাগবে না। আর যদি তিন খুঁটি একই সরলরেখায় পড়ে যায়, তাহলে তো জমিই নেই (একটা সরু রেখা) — area 0।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

114-এ আমরা cross product রাশি (Bx−Ax)(Cy−Ay) − (By−Ay)(Cx−Ax)-এর সাথে পরিচিত হয়েছি — সেখানে শুধু দেখেছি এটা 0 কি না (collinear)।

আজ আমরা সেই একই রাশির মান নিচ্ছি। 0 হলে area 0 (তিন point এক লাইনে, triangle নেই) — মানে collinearity আসলে "area = 0"-এরই আরেক নাম! তাই 114 আর 115 একই সূত্রের দুই চেহারা: 114 জিজ্ঞেস করে "শূন্য?", 115 জিজ্ঞেস করে "কত?"। এই ধারাবাহিকতা মাথায় রাখলে cross product একটাই অস্ত্র, অনেক প্রশ্নের উত্তর।

ভেতরের অঙ্ক

মূল idea shoelace (জুতার ফিতার মতো আড়াআড়ি গুণ)। তিন point A, B, C-র জন্য:

উদাহরণ
doubled area = |(Bx − Ax)(Cy − Ay) − (By − Ay)(Cx − Ax)|
area = doubled area / 2

ভেতরের রাশিটা ঠিক 114-এর cross product — দুটো vector AB আর AC দিয়ে বানানো parallelogram-এর (signed) area। triangle তার অর্ধেক, তাই /2। abs লাগে কারণ point-গুলো ঘড়ির কাঁটার দিকে (CW) সাজানো থাকলে রাশিটা negative আসে — চিহ্নটা আসলে ঘোরার দিক বলে, সেটাও কাজে লাগে (116-এ)।

সৌন্দর্য: পুরোটা integer (input integer হলে), shoelace-এর মান doubled area। আসল area দরকার হলে তবেই /2।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথমে স্কুলের ½ × base × height মাথায় আসে। base হিসেবে AB নিয়ে, এর দৈর্ঘ্য আর C থেকে AB লাইনের লম্ব দূরত্ব দরকার:

Python
import math

def area_bad(a, b, c):
    base = math.dist(a, b)                       # AB-র দৈর্ঘ্য (sqrt!)
    # C থেকে AB লাইনের লম্ব দূরত্ব — line equation দিয়ে
    num = abs((b[1]-a[1])*c[0] - (b[0]-a[0])*c[1] + b[0]*a[1] - b[1]*a[0])
    den = math.dist(a, b)                        # আবার sqrt
    height = num / den
    return 0.5 * base * height

এটা ঠিক উত্তরই দেয়, কিন্তু দুটো sqrt আর একটা ভাগ — তিনটাই float, আর height-এর সূত্রটা মনে রাখাও কঠিন।

কোথায় বেশি কাজ হতে পারে

"slow" নয় ঠিক, বরং অপ্রয়োজনীয় float আর জটিল:

উদাহরণ
brute force: base = sqrt(...), height = num / sqrt(...)
             -> base * height-এ sqrt গুলো কাটাকাটি যায়,
                মানে আমরা ঘুরিয়ে আসলে num/2-ই পাচ্ছি!

shoelace   : সরাসরি |cross| / 2     (কোনো sqrt নেই, integer doubled area)

মজার ব্যাপার — brute force-এ base × height করলে sqrt গুলো নিজেরাই কাটাকাটি হয়ে যায়, আর হাতে থাকে ঠিক shoelace-এর |cross|/2। তাহলে sqrt-এর ঝামেলায় গিয়ে লাভ কী? সরাসরি cross product নাও।

আরও ভালোভাবে ভাবা

মূল insight: triangle area = parallelogram area-র অর্ধেক, আর parallelogram area = cross product-এর মান। তাই height-টিকটিকি বাদ, সরাসরি:

Python
def doubled_area(a, b, c):
    return abs((b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0]))

abs নেওয়ার আগের রাশিটা signed (ঘোরার দিকসহ); area চাইলে abs, তারপর /2। যতক্ষণ পারো doubled area-তেই থাকো — integer, নিখুঁত।

ভাবনার পরিবর্তন

আসল "আহা!": area-কে অর্ধেক না করে "doubled area"-তেই কাজ চালাও — integer থাকে, আর /2 শুধু একদম শেষে, যদি আসল মান ছাপতে হয়।

আর তার চেয়েও বড় tweak — collinearity, area, orientation সব একই cross product। 114 জিজ্ঞেস করেছে "শূন্য কি?", 115 জিজ্ঞেস করছে "কত?", আর 116 জিজ্ঞেস করবে "চিহ্ন কী?"। তিন প্রশ্ন, এক রাশি। এই ঐক্যটা ধরতে পারলে geometry অনেক হালকা লাগবে।

ছবিতে বোঝা

cross product = AB আর AC দিয়ে বানানো parallelogram-এর area; triangle তার ঠিক অর্ধেক:

উদাহরণ
y
3 |        C(4,3)
2 |       /  \
1 |      / tri \         AB = (4,0),  AC = (4,3)
0 |  A(0,0)----B(4,0)    cross = 4*3 - 0*4 = 12
  +------------------ x  doubled area = 12
     0  1  2  3  4       area = 12 / 2 = 6.0

parallelogram (AB, AC):  area 12   ┐
triangle ABC          :  area  6   ┘ ঠিক অর্ধেক

লক্ষ করো — cross product 12 হলো parallelogram-এর পুরো area (= doubled triangle area), আর triangle তার অর্ধেক, 6। এই "doubled-এ থাকো, শেষে অর্ধেক" অভ্যাসটা integer-নিরাপদ।

ছোট input-এ ধাপে ধাপে

চলো A=(0,0), B=(4,0), C=(4,3) নিয়ে area বের করি:

  1. শুরুর অবস্থা: A=(0,0), B=(4,0), C=(4,3)
  2. Bx − Ax = 4 − 0 = 4
  3. Cy − Ay = 3 − 0 = 3
  4. প্রথম গুণ: 4 * 3 = 12
  5. By − Ay = 0 − 0 = 0
  6. Cx − Ax = 4 − 0 = 4
  7. দ্বিতীয় গুণ: 0 * 4 = 0
  8. cross = 12 − 0 = 12 (signed)
  9. doubled area = abs(12) = 12
  10. শেষ অবস্থা: আসল area = 12 / 2 = 6.0

প্রতিটা ধাপ integer; শুধু ধাপ 10-এ এসে /2। collinear হলে ধাপ 8-এ cross = 0 আসত → area 0।

কোড ও ব্যাখ্যা

Python

Python
def doubled_area(a, b, c):
    """triangle ABC-র ক্ষেত্রফলের দ্বিগুণ (integer থাকে) — abs নেওয়া।"""
    return abs((b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]))


def signed_doubled_area(a, b, c):
    """signed (চিহ্নসহ) doubled area — চিহ্ন ঘোরার দিক বলে (116-এ লাগবে)।"""
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


def triangle_area(a, b, c):
    """আসল ক্ষেত্রফল — শুধু এখানে এসে 2 দিয়ে ভাগ।"""
    return doubled_area(a, b, c) / 2


def is_degenerate(a, b, c):
    """area 0 মানে তিন point এক লাইনে — triangle-ই নেই।"""
    return doubled_area(a, b, c) == 0


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert doubled_area((0, 0), (4, 0), (4, 3)) == 12
assert doubled_area((0, 0), (4, 0), (0, 3)) == 12      # সমকোণী
assert doubled_area((0, 0), (2, 0), (1, 1)) == 2
assert doubled_area((0, 0), (1, 1), (2, 2)) == 0       # collinear -> 0

assert triangle_area((0, 0), (4, 0), (4, 3)) == 6.0
assert triangle_area((0, 0), (2, 0), (1, 1)) == 1.0

# চিহ্ন: CCW ধনাত্মক, CW ঋণাত্মক, কিন্তু মান এক
assert signed_doubled_area((0, 0), (4, 0), (2, 3)) == 12    # CCW
assert signed_doubled_area((0, 0), (2, 3), (4, 0)) == -12   # CW (উল্টো ক্রম)

assert is_degenerate((0, 0), (1, 1), (2, 2)) is True       # এক লাইনে
assert is_degenerate((0, 0), (4, 0), (4, 3)) is False

print(doubled_area((0, 0), (4, 0), (4, 3)))   # 12
print(triangle_area((0, 0), (4, 0), (4, 3)))  # 6.0
print(is_degenerate((0, 0), (1, 1), (2, 2)))  # True
print("সব test pass!")

কোডের প্রতিটি অংশ

উদাহরণ
def doubled_area(a, b, c):
    return abs((b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]))

ভেতরের রাশি ঠিক 114-এর cross product — AB আর AC দিয়ে বানানো parallelogram-এর signed area। abs নিয়ে আমরা মান পাই, যা triangle-এর দ্বিগুণ ক্ষেত্রফল। পুরোটা integer।

উদাহরণ
def signed_doubled_area(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

abs ছাড়া — চিহ্নটা রেখে দিই। ধনাত্মক মানে CCW, ঋণাত্মক মানে CW। 116-এ এই চিহ্নই orientation দেবে।

উদাহরণ
def triangle_area(a, b, c):
    return doubled_area(a, b, c) / 2

আসল area চাইলে এখানেই, একদম শেষে, 2 দিয়ে ভাগ — তাই দরকারে float।

উদাহরণ
def is_degenerate(a, b, c):
    return doubled_area(a, b, c) == 0

doubled area 0 মানে তিন point এক লাইনে (114-এর collinear!) — তাই triangle নেই।

বাকি assert লাইনগুলো নিজেদের যাচাই করছে; সব মিললে শেষে সব test pass!।

Output মিলিয়ে দেখা

চালালে যা ছাপবে:

উদাহরণ
12
6.0
True
সব test pass!

প্রথম লাইন: doubled area 12 (integer)। দ্বিতীয়: আসল area 6.0। তৃতীয়: (0,0),(1,1),(2,2) এক লাইনে → degenerate → True। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(1) — তিনটা point-এর জন্য কয়েকটা বিয়োগ-গুণ-বিয়োগ। (n-কোণা polygon-এ shoelace হবে O(n) — প্রতিটা ধার একবার, যেটা 124-এ লাগবে।)

অতিরিক্ত জায়গা

O(1) — শুধু গুটিকয় মান হিসাব করছি, কোনো বাড়তি list/array নেই।

যে ভুলগুলো এড়াতে হবে

  1. abs নিতে ভুলে যাওয়া — CW ক্রমে রাশি negative আসে; area চাইলে abs, নাহলে ঋণাত্মক area পাবে।
  2. /2 নিতে ভুলে যাওয়া — cross product হলো doubled area; আসল area অর্ধেক।
  3. খুব তাড়াতাড়ি /2 করে float-এ চলে যাওয়া — যতক্ষণ পারো doubled (integer)-এ থাকো; তুলনা/যোগে এটা নিরাপদ, ভাগ শুধু একদম শেষে।
  4. collinear case ভুলে যাওয়া — তিন point এক লাইনে হলে area 0; এটা ভুল নয়, এটাই সঠিক (triangle নেই)।
  5. point-এর ক্রম নিয়ে দুশ্চিন্তা — area-র জন্য ক্রম গুরুত্বহীন (abs নিলে); শুধু signed দরকার হলেই ক্রম/চিহ্ন খেয়াল রাখো।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

  • CSES — Polygon Area (https://cses.fi/problemset/task/2191) — n-কোণা polygon-এ shoelace-এর সরাসরি প্রয়োগ; doubled area integer-এ রাখাই মূল কৌশল।
  • LeetCode — Largest Triangle Area (https://leetcode.com/problems/largest-triangle-area/) — সব triple-এর shoelace area, সবচেয়ে বড়টা।
  • 124 (Pick's Theorem Intro) — এই repo-রই পরের ধাপ, যেখানে shoelace area থেকে ভেতরের lattice point গোনা হবে।

কৌশলটি মনে রাখুন

Shoelace / cross product for area — triangle area = |cross(AB, AC)| / 2; যতক্ষণ পারো doubled area (integer)-এ থাকো, /2 শেষে। বড় শিক্ষা: collinearity (cross = 0), area (cross-এর মান), orientation (cross-এর চিহ্ন) — সব একই cross product-এর তিন প্রশ্ন।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "triangle area = |cross(AB,AC)|/2; doubled area integer-এ রাখো, /2 শেষে। আর মনে রেখো — collinearity হলো area = 0; এক cross product, তিন প্রশ্ন (শূন্য? কত? চিহ্ন?)।"

পরের ধাপ → 116 — Orientation of Three Points (এবার cross product-এর চিহ্ন — level-এর কেন্দ্র)। শিকড় → 114 — Slope and Collinearity। সম্পর্কিত → 124 — Pick's Theorem Intro।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।