Giải bài tập chương trình đồ họa vẽ hình tròn bằng C/C++

Giải bài tập chương trình đồ họa vẽ hình tròn bằng C/C++

Quang viết một chương trình đồ họa, chương trình đó vẽ n hình tròn màu trắng lên màn hình màu đen. Màn hình là màn hình đen trắng có độ phân giải là w * h pixels. Pixels được đánh số từ góc trên bên trái (0,0) tới góc dưới bên phải (w-1,h-1).

Một hình tròn có tâm O(xc,yc) bán kính r chứa các pixel có tọa độ (x,y) thỏa mãn

sqrt((xc -x)*(xc -x) +(yc -y)*(yc -y)) ≤ r. Nếu hình tròn tràn quá màn hình thì hình tròn đó sẽ bị cắt.

Nếu một điểm cùng thuộc hai hay nhiều hình tròn thì điểm đó có màu trắng.

Quang khá hài lòng với bức tranh được vẽ ra, vì vậy Quang quyết định vẽ bức tranh đó lên bức tường màu trắng trong phòng ngủ của mình, và anh ấy chỉ vẽ một phần bức tranh bằng màu đen. Bây giờ Quang muốn biết số lượng màu đen anh ấy cần. Quang copy bức tranh theo ánh xạ pixel - to - pixel. Vì vậy anh ấy viết chương trình tính số lượng pixel màu đen trên màn hình sau khi vẽ n hình tròn.

ve hinh tron

[Input]

* Dữ liệu đầu vào được được ghi trong file "CIRCLES.INP"

* Dòng đầu tiên chứa 3 số nguyên dương: w, h và n (1 ≤ w, h ≤ 20 000; 1 ≤ n ≤ 100). n dòng tiếp theo mô tả hình tròn với tâm (xi, yi) và bán kính r.

[Output]

* Ghi số lượng pixel màu đen còn lại trên màn hình ra file "CIRCLES.OUT".

[Input example]

5 3 2
1 1 1
3 1 1

[Output example]

6

[Giải thuật]

* Với mỗi hình tròn tâm (x,y) bán kính r luôn được bao phủ bởi một hình chữ nhật có cạnh trái là đoạn thẳng đi qua điểm  (x - r, y), có cạnh phải là đoạn thẳng đi qua điểm (x + r, y), cạnh trên là đoạn thẳng đi qua điểm (x, y -r), có cạnh đáy đi qua điểm (x, y + r).

ve hinh tron

* Duyệt tất cả các điểm nằm trong hình chữ nhật ở trên nếu điểm đó thỏa mãn: sqrt((xc -x)*(xc -x) +(yc -y)*(yc -y)) ≤ r  thì điểm đó nằm trong hình tròn và đánh dấu pixel đó là trắng đồng thời tăng biến đếm số pixel trắng lên 1, ngược lại điểm đó không nằm trong hình tròn.

* Duyệt tất cả các hình tròn theo cách trên để đếm số điểm trắng được bao phủ bởi tất cả hình tròn.

* Số điểm đen không được tô trắng bằng số pixel của màn hình trừ đi số điêm trắng, đây là kết quả cần tìm của bài toán.

Chương trình cài đặt bằng C/C++

#include<iostream>

#include <cstdio>

using namespace std;

#define WMAX 20001

#define HMAX 20001

#define max(a,b) a > b ? a:b

#define min(a,b) a > b ? b:a

bool matrix[WMAX][HMAX];

int main(){

 freopen("CIRCLES.INP", "r", stdin);

 freopen("CIRCLES.OUT", "w", stdout);

 int w, h, n;

 cin >> w >> h >> n;

 int  countWhite = 0;

 int rightRecX, leftRecX, bottomRecY, topRecY;

 int centerX, centerY, radius;

 for (int i = 0; i<n; i++){

  cin >> centerX >> centerY >> radius;

  //so sánh cạnh bên trái của hình chữ nhật với oy.

  leftRecX = max(0, centerX - radius);

  //so sánh cạnh bên phải của hình chữ nhật với đường thẳng đi qua điểm x = w -1.

  rightRecX = min(w - 1, centerX + radius);

  //so sánh cạnh đáy của hình chữ nhật với ox.

  bottomRecY = max(0, centerY - radius);

  //so sánh cạnh trên của hình chữ nhật với đường thẳng đi qua điểm y = h-1.

  topRecY = min(h - 1, centerY + radius);

  for (int x = leftRecX; x <= rightRecX; x++){

   for (int y = bottomRecY; y <= topRecY; y++){

    if (matrix[x][y] == false && ((centerX - x)*(centerX - x) + (centerY - y)*(centerY - y) <= radius*radius)){

     matrix[x][y] = true;

     countWhite++;

    }

   }

  }

 }

 cout << (w*h - countWhite) << endl;

 return 0;

}

 

Bạn thấy bài viết này như thế nào?: 
No votes yet
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Lợi ích đem lại từ Rich Snippets

Lợi ích đem lại từ Rich Snippets

Chắc hẳn bạn đã từng thấy một số kết quả tìm kiểm hiển thị trên Google được gắn sao khi bạn tìm kiếm với từ khóa nào đó? Đó chính là Rich Snippets. Ở bài viết này chúng tôi sẽ giới thiệu về Rich Snippets và những lợi ích mà nó đem lại.

Dịch vụ diệt muỗi tận gốc tại nhà tháng 03 năm 2016

Dịch vụ diệt muỗi tận gốc tại nhà tháng 03 năm 2016

Thông thường dịch vụ diệt muỗi sẽ được bảo hành trong 03 tháng tính từ ngày thực hiện phun thuốc.

Facebook muốn phủ sóng toàn thế giới

Facebook muốn phủ sóng toàn thế giới

Mạng xã hội hùng mạnh nhất thế giới hiện có khoảng 800 triệu thành viên, nhưng mục tiêu của Facebook không dừng lại ở đó.