#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
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);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
