พื้นที่สี่เหลี่ยมผืนผ้า II ใน C++

สมมติว่าเรามีรายการสี่เหลี่ยม (จัดแนวแกน) รูปสี่เหลี่ยมผืนผ้าแต่ละรูป[i] ={x1, y1, x2, y2} โดยที่ (x1, y1) คือจุดที่มุมล่างซ้าย และ (x2, y2) เป็นจุดมุมบนขวาของ ด้วยสี่เหลี่ยม

เราต้องหาพื้นที่รวมของสี่เหลี่ยมทั้งหมดในระนาบ คำตอบอาจจะมาก ดังนั้นเราจึงสามารถใช้โมดูโล 10^9 + 7

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 6.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม. =10^9 + 7

• กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,

• กลับ ((a mod m) + (b mod m) mod m)

• กำหนดหนึ่งฟังก์ชันบีบอัดซึ่งจะใช้เมทริกซ์ 2d v

• กำหนดอุณหภูมิอาร์เรย์

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ใส่ v[i, 0] ที่จุดสิ้นสุดของอุณหภูมิ

  • ใส่ v[i, 2] ที่จุดสิ้นสุดของอุณหภูมิ

• จัดเรียงอุณหภูมิอาร์เรย์

• กำหนดหนึ่งแผนที่ ret

• idx :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า temp[i] ไม่ได้เป็นสมาชิกของ ret แล้ว −

    • ret[temp[i]] :=idx

    • (เพิ่ม idx ขึ้น 1)

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดอาร์เรย์ xv

• แทรก { 0 } ที่ส่วนท้ายของ xv

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ใส่ v[i, 0] ต่อท้าย xv

  • ใส่ v[i, 2] ต่อท้าย xv

• เรียงลำดับอาร์เรย์ xv

• uniItr =องค์ประกอบแรกของรายการที่มีองค์ประกอบเฉพาะของ xv

• ลบ uniItr จาก xv

• กำหนดดัชนีแผนที่หนึ่งรายการ

• idx :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ดัชนี[xv[i]] :=ผม

• กำหนดจำนวนอาร์เรย์ที่มีขนาดเท่ากับขนาดดัชนี

• กำหนดอาร์เรย์ 2 มิติ x

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • x1 :=v[i, 0], y1 :=v[i, 1]

  • x2 :=v[i, 2], y2 :=v[i, 3]

  • ใส่ { y1, x1, x2, 1 } ต่อท้าย x

  • แทรก { y2, x1, x2, -1 } ที่ส่วนท้ายของ x

• เรียงลำดับอาร์เรย์ x

• ยกเลิก :=0

• ผลรวม :=0, ปัจจุบันY :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • y :=x[i, 0]

  • x1 :=x[i, 1], x2 :=x[i, 2]

  • sig :=x[i, 3]

  • ret :=add(ret, (y - currentY) * sum)

  • ปัจจุบันY :=y

  • สำหรับการเริ่มต้น i :=index[x1] เมื่อฉัน

    • นับ[i] :=นับ[i] + ซิก

  • ผลรวม :=0

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดการนับ อัปเดต (เพิ่ม i ขึ้น 1) ทำ −

    • ถ้านับ[i]> 0 แล้ว

      • ผลรวม :=ผลรวม + (xv[i + 1] - xv[i])

• คืนค่า ret mod m

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;typedef long long int lli;const int m =1e9 + 7;class Solution { สาธารณะ:lli add(lli a, lli b){ return ((a % ม.) + (b % ม.) % ม.); } แผนที่  บีบอัด (เวกเตอร์<เวกเตอร์>&v){ เวกเตอร์ อุณหภูมิ; สำหรับ (int i =0; i  ret; int idx =0; สำหรับ (int i =0; i >&v){ vector xv; xv.push_back({ 0 }); สำหรับ (int i =0; i ::iterator uniItr =ไม่ซ้ำกัน(xv.begin(), xv.end()); xv.erase(uniItr, xv.end()); แผนที่  ดัชนี; int idx =0; สำหรับ (int i =0; i  count(index.size()); เวกเตอร์<เวกเตอร์> x; x1, x2, y1, y2; สำหรับ (int i =0; i  0) { sum +=(xv[i + 1] - xv[i]); } } } ผลตอบแทนย้อนหลัง % m; }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{0,0,2,2},{1,0,2,3},{1,0,3,1}}; ศาล <<(ob.rectangleArea(v));}

อินพุต

ผลลัพธ์

6