1139 : อาคารเรียน (campus)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)
ณ สถาบันเทคโนโลยีแห่งหนึ่งทางภาคตะวันออกเฉียงเหนือ มีหอพักอยู่ทั้งหมด N หอ ตั้งอยู่บนพิกัดที่เป็นจำนวนเต็มบนระนาบสองมิติ แต่ละหอก็มีนักเรียนจำนวนหนึ่งพักอยู่
วันหนึ่ง ทางสถาบันได้วางแผนที่จะสร้างอาคารเรียนแห่งใหม่ขึ้นมา 1 อาคาร ซึ่งต้องตั้งอยู่บนพิกัดที่เป็นจำนวนเต็มเช่นกัน โดยต้องการให้ระยะทางรวมที่นักเรียนทุกคนใช้ในการเดินไปเรียนมีค่าน้อยที่สุดเท่าที่จะทำได้
เนื่องจากทางเดินในสถาบันแห่งนี้มีลักษณะเป็นตารางสี่เหลี่ยมจัตุรัส หากหอพักของนักเรียนตั้งอยู่ที่พิกัด (x1, y1) และอาคารเรียนตั้งอยู่ที่พิกัด (x2, y2) นักเรียนจะต้องเดินมาเรียนเป็นระยะทาง |x1 - x2| + |y1 - y2| นอกจากนี้ หอพักแต่ละหอยังมีขนาดเล็กมาก จึงอาจมีหอพักมากกว่า 1 หอ ตั้งอยู่ที่พิกัดเดียวกันได้ และตำแหน่งที่จะสร้างอาคารเรียน อาจตรงกับพิกัดของหอพักบางหอก็ได้
งานของคุณ
จงเขียนโปรแกรมเพื่อรับตำแหน่งที่ตั้งและจำนวนนักเรียนในหอพักแต่ละหอ แล้วคำนวณหาระยะทางรวมที่น้อยที่สุดที่นักเรียนทุกคนใช้ในการเดินไปเรียน
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (1 ≤ N ≤ 500,000) แทนจำนวนหอพักทั้งหมด
อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) ระบุจำนวนเต็ม Xi, Yi และ Si (1 ≤ Xi,Yi ≤ 1,000,000,000; 1 ≤ Si ≤ 1,000) แทนพิกัดบนแกน X พิกัดบนแกน Y และจำนวนนักเรียนในหอพักที่ i
ข้อมูลส่งออก
มีบรรทัดเดียว แทนระยะทางรวมที่น้อยที่สุดที่นักเรียนทุกคนใช้ในการเดินไปเรียน
การให้คะแนน
30% ของข้อมูลทดสอบ จะมี Si = 1 สำหรับทุกจำนวนเต็ม i (1 ≤ i ≤ N )
60% ของข้อมูลทดสอบ จะมี N ≤ 100,000
20% ของข้อมูลทดสอบ จะสอดคล้องกับเงื่อนไขด้านบนทั้งสองข้อ
ที่มา
โจทย์โดย: สุธี เรืองวิเศษ
วันหนึ่ง ทางสถาบันได้วางแผนที่จะสร้างอาคารเรียนแห่งใหม่ขึ้นมา 1 อาคาร ซึ่งต้องตั้งอยู่บนพิกัดที่เป็นจำนวนเต็มเช่นกัน โดยต้องการให้ระยะทางรวมที่นักเรียนทุกคนใช้ในการเดินไปเรียนมีค่าน้อยที่สุดเท่าที่จะทำได้
เนื่องจากทางเดินในสถาบันแห่งนี้มีลักษณะเป็นตารางสี่เหลี่ยมจัตุรัส หากหอพักของนักเรียนตั้งอยู่ที่พิกัด (x1, y1) และอาคารเรียนตั้งอยู่ที่พิกัด (x2, y2) นักเรียนจะต้องเดินมาเรียนเป็นระยะทาง |x1 - x2| + |y1 - y2| นอกจากนี้ หอพักแต่ละหอยังมีขนาดเล็กมาก จึงอาจมีหอพักมากกว่า 1 หอ ตั้งอยู่ที่พิกัดเดียวกันได้ และตำแหน่งที่จะสร้างอาคารเรียน อาจตรงกับพิกัดของหอพักบางหอก็ได้
งานของคุณ
จงเขียนโปรแกรมเพื่อรับตำแหน่งที่ตั้งและจำนวนนักเรียนในหอพักแต่ละหอ แล้วคำนวณหาระยะทางรวมที่น้อยที่สุดที่นักเรียนทุกคนใช้ในการเดินไปเรียน
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (1 ≤ N ≤ 500,000) แทนจำนวนหอพักทั้งหมด
อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) ระบุจำนวนเต็ม Xi, Yi และ Si (1 ≤ Xi,Yi ≤ 1,000,000,000; 1 ≤ Si ≤ 1,000) แทนพิกัดบนแกน X พิกัดบนแกน Y และจำนวนนักเรียนในหอพักที่ i
ข้อมูลส่งออก
มีบรรทัดเดียว แทนระยะทางรวมที่น้อยที่สุดที่นักเรียนทุกคนใช้ในการเดินไปเรียน
การให้คะแนน
30% ของข้อมูลทดสอบ จะมี Si = 1 สำหรับทุกจำนวนเต็ม i (1 ≤ i ≤ N )
60% ของข้อมูลทดสอบ จะมี N ≤ 100,000
20% ของข้อมูลทดสอบ จะสอดคล้องกับเงื่อนไขด้านบนทั้งสองข้อ
ที่มา
โจทย์โดย: สุธี เรืองวิเศษ
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 4 1 2 1 2 1 1 2 3 1 3 2 1 | 4 |
| 3 1 1 1 6 3 3 4 8 2 | 21 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 22 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)