Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

STEEL - Khuôn thép




Để chuẩn bị cho Lễ hội kỷ niệm 30 năm ngày Chiến dịch Hồ Chí Minh toàn thắng, giải phóng miền Nam, thống nhất đất nước, người ta cần gia công các loại khuôn thép có hình dạng là các hình đa giác lồi M đỉnh. Mỗi khuôn thép được thiết kế trên một tấm thép cũng có hình dạng là một hình đa giác lồi N đỉnh, không có cạnh nào của khuôn thép nằm gọn trên một cạnh của tấm thép. Để tiện cho việc gia công, khuôn thép được vẽ sao cho hai đường thẳng chứa hai cạnh không kề nhau của nó không cắt nhau ở bên trong tấm thép.

Công việc chính cần làm trong quá trình gia công là sử dụng máy cắt để cắt được khuôn thép từ tấm thép ra. Rõ ràng là cần phải thực hiện M nhát cắt. Mỗi nhát cắt được thực hiện bằng cách chọn một cạnh nào đó của khuôn thép và cắt theo đường thẳng chứa cạnh ấy chia tấm thép thành hai phần, một phần chứa khuôn thép cần gia công. Chi phí cắt khuôn thép là tổng chiều dài của các đường cắt.

Hình minh họa

Trên hình 1 và 2, tấm thép là tứ giác được tô nhạt, khuôn thép là hình vuông được tô bằng các gạch đậm. Các nét gạch đứt là các đường cắt với tổng chi phí bằng 6.5 đơn vị.

Yêu cầu: Cho biết hình dạng tấm thép và khuôn thép cần gia công. Hãy tìm phương án cắt khuôn thép có chi phí nhỏ nhất.

Dữ liệu

Dòng đầu ghi số N là số đỉnh của tấm thép; dòng tiếp theo, mỗi dòng ghi 2 số thực x và y, là toạ độ N đỉnh của tấm thép được liệt kê theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đó; dòng tiếp theo ghi số M là số đỉnh của khuôn thép; cuối cùng là M dòng, mỗi dòng ghi 2 số thực x và y là toạ độ M đỉnh của khuôn thép được liệt kê theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đó. Các số trên một dòng cách nhau ít nhất một dấu cách.

Kết qủa

Gồm một dòng duy nhất là chi phí nhỏ nhất tìm được với độ chính xác tới 4 chữ số sau dấu chấm thập phân.

Giới hạn

  • 3 ≤ N ≤ 2000
  • 3 ≤ M ≤ 2000
  • -104 < x, y < 104

Ví dụ

Dữ liệu:
4
2 1 
2 5  
5 3.5  
5 2
4
3 3 
3 4 
4 4 
4 3  
Kết qủa
6.5000
Submit solution!
Được gửi lên bởi:Jimmy
Ngày:2007-12-01
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Đề thi quốc gia 2005
hide comments
Xem lại 1  2 Xem tiếp >
2021-11-16 05:31:05
Input

3

3

0 1 2

1 2

1 2 2

0 2

2 3 2

0 1

7

0 1 2

2 3

1 2 2

3 4

2 3 2

0 5

3 1 4

0 1 5 6

4 2 2

1 6

5 3 2

2 3

6 1 2

3 4

4

0 1 2

1 2

1 8 2

0 3

2 16 2

0 3

3 12 2

1 2

Output

Case #1

3

Case #2

4

Case #3

9


#include <iostream>
using namespace std;
int M, u_min, v_min, minmin, result;
int map[106][106];
int visited[106];
int mbd[106];
int parent[106];
bool cochutrinh;

void format() {
for(int i = 0; i < M; i++) {
visited[i] = 0;
parent[i] = -1;
}
}

void find_min(int stop_node, int dinh) {
if(dinh == stop_node) {
result += minmin;
map[u_min][v_min] = map[v_min][u_min] = 0;
format();
return;
}
else
{
if(minmin > mbd[dinh] + mbd[parent[dinh]]) {
u_min = dinh;
v_min = parent[dinh];
minmin = mbd[dinh] + mbd[parent[dinh]];

}
find_min(stop_node, parent[dinh]);
}
}

void DFS(int dinh) {

visited[dinh] = 1;

for(int v = 0; v < M; v ++) {
if ( map[dinh][v] != 0)
{
if(visited[v] == 0) {
if (!cochutrinh) {
parent[v] = dinh;
DFS(v);
}
}
else if (parent[dinh] != v)
{
cochutrinh = true;
minmin = mbd[dinh] + mbd[v];
u_min = dinh; v_min = v;
find_min(v, dinh);
}
}
}
}

int main() {
freopen("input.txt", "r", stdin);
int t; cin >> t;

for(int tc = 1; tc <= t; tc++) {
cin >> M;

for(int i = 0; i < M; i++) {
for(int j = 0; j < M; j++) {
map[i][j] = 0;
}
}

for(int i = 0; i < M; i++) {
int a, c, u;
cin >> a;
cin >> mbd[a] >> c;
for(int j = 1; j <= c; j ++) {
cin >> u;
map[a][u] = map[u][a] = 1;
}
}

result = 0;
for(int u = 0; u < M; u ++) {
do {
cochutrinh = false;
format();
DFS(u);
}
while( cochutrinh);
}

cout << "Case #" << tc << endl;
cout << result << endl;
}
return 0;
}
2021-11-15 09:22:00
package Earningbig;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {

static String a;
static int Anwser;
static char num[]=new char [1000];
static int value=0;
static int ex;
static int exChange;
static int visit[][]=new int [11][10000009];
static int tc;




public static void doChange(int ex, char num[]) {
value =0;
for(int i=0;i<a.length();i++) {
value=value*10+num[i]-48;

}
if(visit[ex][value]==tc) {
return;
}

visit[ex][value]=tc;
char temp[]=new char[10];
char c;
if(ex==exChange) {
Anwser=value>Anwser ? value:Anwser;
}
else {
for(int i=0;i<a.length();i++) {
for(int j=i+1;j<a.length();j++) {
for(int l=0;l<a.length();l++) {
temp[l]=num[l];
}
c=temp[i];
temp[i]=temp[j];
temp[j]=c;
doChange(ex+1,temp);


}
}

}


}

public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
Scanner sc =new Scanner (new FileInputStream("D:\\trung.txt"));
int T;
T=sc.nextInt();
sc.nextLine();
for( tc=1;tc<=T;tc++) {



a=sc.next();
exChange=sc.nextInt();
for(int i=0;i<a.length();i++) {
num[i]=a.charAt(i);
}

Anwser=0;
doChange(0, num);
System.out.println("Case"+" #"+tc);
System.out.println(Anwser);




}
}

}
2021-08-21 03:07:22
nxhieu Hai Phong vo doi

Last edit: 2021-08-21 03:16:21
2020-10-23 10:36:09
đề này không cần nghĩ - Hoàng Vũ A2K48 2020
2018-09-04 10:46:48
Ánh sáng của Đảng đã soi sáng em AC
2016-12-15 16:51:48
2 dòng AC, dễ vc
2016-11-14 09:27:07
Đề như nồn

Last edit: 2016-11-14 09:29:07
2016-11-14 08:59:46
Vét cũng AC
2016-11-14 08:59:40 le tuan dung


Last edit: 2016-11-14 09:00:03
2016-11-14 08:58:03
Được boss Tùng sp chắc AC cmnr

Last edit: 2016-11-14 08:58:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.