Submission #72494

#	Time	Username	Problem	Language	Result	Execution time	Memory
72494		BOJ 8481 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	0 / 100	5 ms	2680 KiB

hill

#include <stdio.h>
#include <queue>
#include <functional>
using namespace std;
int n,si;
int siment;
int x[100010];
int y[100010];
int gcd(int xx, int yy){
	return xx%yy==0 ? yy : gcd(yy, xx%yy);
}
class Point{
public:
	int x;
	int y;
	Point(){
		x = y = 0;
	}
	Point(int x1, int y1){
		x = x1;
		y = y1;
	}
};
Point arr[100010];
class Hill{
public:
	int dx;
	int dy;
	int s;
	int e;
	Hill(){
		dx = dy = s = e = 0;
	}
	Hill(int i, int j){
		dx = arr[j].x - arr[i].x;
		dy = arr[j].y - arr[i].y;
		s = i;
		e = j;
	}
	Hill(int dx1, int dy1, int s1, int e1){
		dx = dx1, dy = dy1, s = s1, e = e1;
	}
};
bool Comp(Hill a, Hill b){
	return a.dx * b.dy > a.dy * b.dx;
}
bool equal(Hill a, Hill b){
	return a.dx * b.dy == a.dy * b.dx;
}
int area(Point a, Point b, Point c){
	return (c.x - a.x) * (c.y + a.y) - (c.x - b.x) * (c.y + b.y) - (b.x - a.x) * (b.y + a.y);
}
priority_queue<Hill, vector<Hill>, function<bool(Hill, Hill)> > q(Comp);
Hill store[100010];
int prev_pointer[100010];
int main(){
	scanf("%d%d", &n, &si);
	siment = 2 * si;
	for(int i=1; i<=n; i++) scanf("%d", &arr[i].x);
	for(int i=1; i<=n; i++) scanf("%d", &arr[i].y);
	for(int i=1; i<n; i++){
		// Hill temp = Hill(arr[i+1].x - arr[i].x, arr[i+1].y - arr[i].y, i, i+1);
		Hill temp = Hill(i, i+1);
		q.push(temp);
		store[i] = temp;
		prev_pointer[i+1] = i;
	}
	while(siment > 0 && q.size() > 1){
		auto temp = q.top();
		q.pop();
		if(temp.s == 1) continue;
		if(!equal(temp, store[temp.s])) continue;

		int a = prev_pointer[temp.s];
		int b = temp.s;
		int c = temp.e;

		siment -= area(arr[a], arr[b], arr[c]);
		prev_pointer[c] = prev_pointer[b];
		Hill newhill = Hill(a, c);
		q.push(newhill);
		store[a] = newhill;
	}
	auto result = q.top();
	int g = gcd(result.dx, result.dy);
	printf("%d/%d\n", result.dy / g, result.dx / g);
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &si);
  ~~~~~^~~~~~~~~~~~~~~~~
hill.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d", &arr[i].x);
                          ~~~~~^~~~~~~~~~~~~~~~~
hill.cpp:60:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d", &arr[i].y);
                          ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 32
• Subtask 2: 0 / 68