ตรวจสอบว่าเส้นที่ 45 องศาสามารถแบ่งระนาบออกเป็นสองส่วนน้ำหนักเท่ากันใน C++ . ได้หรือไม่

สมมติว่าเรามีจุดที่แตกต่างกัน n จุด (Xi, Yi) ในพิกัด 2D และแต่ละจุดมีน้ำหนัก Wi เราต้องตรวจสอบว่าสามารถลากเส้นที่ 45 องศาได้หรือไม่ เพื่อให้น้ำหนักรวมของคะแนนในแต่ละด้านเท่ากัน

ดังนั้น หากอินพุตเป็น like[[-1,1,3],[-2,1,1],[1,-1,4]] ผลลัพธ์จะเป็น True/

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

• n :=ขนาดของวี
• กำหนดน้ำหนักหนึ่งแผนที่_at_x
• max_x :=-2000, min_x :=2000
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• temp_x :=v[0, i] - v[1, i]
• max_x :=สูงสุดของ max_x และ temp_x
• min_x :=ขั้นต่ำของ min_x และ temp_x
• weight_at_x[temp_x] :=weight_at_x[temp_x] + v[2, i]

ตัวอย่าง

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

#include ใช้เนมสเปซ std;void is_valid_part(vector> &v){ int n =v.size(); แผนที่ weight_at_x; int max_x =-2000, min_x =2000; สำหรับ (int i =0; i  sum_temp; sum_temp.push_back(0); สำหรับ (int x =min_x; x <=max_x; x++) { sum_temp.push_back(sum_temp.back() + weight_at_x[x]); } int total_sum =sum_temp.back(); int partition_possible =เท็จ; สำหรับ (int i =1; i > v ={{-1,1,3},{-2,1,1},{1 } ,-1,4}}; is_valid_part(v);}

อินพุต

ผลลัพธ์

จริง