— Dark mode

Datatähti Open 2019

Function

  • Start: N/A
  • End: N/A
Submission details
Task:Function
Sender:ruhanhabib39
Submission time:2019-01-19 19:06:19 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.01 s1details
#20.02 s1details
#30.02 s1details
#40.02 s1details
#50.01 s1details
#60.03 s1details
#70.01 s1details
#80.02 s1details
#90.01 s1details
#100.03 s2details
#110.03 s2details
#120.02 s2details
#130.01 s2details
#140.02 s2details
#150.02 s2details
#160.02 s2details
#170.01 s2details
#180.03 s2details
#190.01 s2details
#200.02 s2details
#210.03 s2details
#220.02 s2details
#230.02 s2details
#240.03 s2details
#250.01 s2details
#260.01 s2details
#270.03 s2details
#280.02 s2details
#290.01 s2details
#300.02 s2details
#310.01 s2details
#320.02 s2details
#330.02 s2details
#340.02 s2details
#350.03 s2details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:87:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    freopen("inp.txt", "r", stdin);
    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:88:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int t; scanf("%d", &t);
           ~~~~~^~~~~~~~~~
input/code.cpp:90:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
input/code.cpp:92:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%lld%lld", &p[i].x, &p[i].y);
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e9 + 10;

const int MAXN = 1e6;

struct pts {
   long long x, y;
   pts operator-(pts p) const {
      return pts{x - p.x, y - p.y};
   }
   long long cross(pts p) const {
      return x * p.y - y * p.x;
   }
};

long long gcd(long long a, long long b) {
   if(a == 0) return b;
   return gcd(b % a, a);
}

pair<long long, long long> simplify(pair<long long, long long> f) {
   long long a = f.first, b = f.second;
   if(b == 0) {
      if(a < 0) return {-INF, 1};
      return {INF, 1};
   }
   long long g = gcd(abs(a), abs(b));
   long long aa = a / g, bb = b / g;
   if(bb < 0) {
      aa *= -1;
      bb *= -1;
   }
   return {aa, bb};
}

struct frac {
   long long a, b;
   frac(long long x = 0, long long y = 1) : a(x), b(y) {
      auto pp = ::simplify({a, b});
      a = pp.first;
      b = pp.second;
   }
   frac simplify() const {
      return frac(a, b);
   }
   frac operator+(frac other) const {
      frac res = frac(a * other.b + other.a * b, b * other.b);
      return res.simplify();
   }
   frac operator-(frac other) const {
      frac res = frac(a * other.b - other.a * b, b * other.b);
      return res.simplify();
   }
   bool operator<(frac other) const {
      // a/b < x/y => ay < bx
      return a * other.b < other.a * b;
   }
   bool operator==(frac other) const {
      return a * other.b == other.a * b;
   }
};

int n;
pts p[MAXN + 10];

ostream& operator<<(ostream& os, frac f) {
   return os << f.a << "/" << f.b << "\n";
}

bool solve() {
   if(n <= 3) return true;
   frac mn(-INF), mx(INF);
   for(int i = 0; i+2 < n; i++) {
      frac tan_a = frac(p[i+1].x - p[i].x, p[i+1].y - p[i].y);
      frac tan_b = frac(p[i+2].x - p[i+1].x, p[i+2].y - p[i+1].y);
      if(tan_b < tan_a) swap(tan_a, tan_b);
      if(mn < tan_a) mn = tan_a;
      if(tan_b < mx) mx = tan_b;
   }
   //cerr << mn << " " << mx << "\n";
   return mn < mx;
}

int main() {
   freopen("inp.txt", "r", stdin);
   int t; scanf("%d", &t);
   for(int cs = 1; cs <= t; cs++) {
      scanf("%d", &n);
      for(int i = 0; i < n; i++) {
         scanf("%lld%lld", &p[i].x, &p[i].y);
      }
      if(solve()) printf("YES\n");
      else printf("NO\n");
   }
}

Test details

Test 1

Group: 1

Verdict:

input
12
2
0 0
1 1
5
...
view save

correct output
YES
YES
NO
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 2

Group: 1

Verdict:

input
100
2
92 30
22 44
2
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 3

Group: 1

Verdict:

input
100
3
-55 -98
-59 -55
-2 88
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 4

Group: 1

Verdict:

input
100
4
87 81
-84 42
18 -46
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 5

Group: 1

Verdict:

input
100
1000
-81 38
92 -21
-10 -65
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 6

Group: 1

Verdict:

input
100
110
-99 -9
-98 -9
-96 -8
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 7

Group: 1

Verdict:

input
100
78
-100 95
-99 96
-98 95
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 8

Group: 1

Verdict:

input
100
201
-100 97
-100 96
-99 99
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 9

Group: 1

Verdict:

input
100
45
-100 89
-100 90
-97 90
...
view save

correct output
YES
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 10

Group: 2

Verdict:

input
13
2
0 0
1 1
5
...
view save

correct output
YES
YES
NO
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 11

Group: 2

Verdict:

input
100
2
-517113909 -39540276
-209411537 -831819487
2
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 12

Group: 2

Verdict:

input
100
3
-991349544 139282777
646238126 16140762
-4488261 817588303
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 13

Group: 2

Verdict:

input
100
4
891187584 -889373775
-453505448 -469134344
-683807769 8725517
...
view save

correct output
YES
NO
YES
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 14

Group: 2

Verdict:

input
100
1000
-866614983 -994037153
775605588 -328510132
390868551 927606059
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 15

Group: 2

Verdict:

input
100
1000
-911073332 -1000000000
-905159999 -1000000000
-904949593 -999999999
...
view save

correct output
YES
YES
YES
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 16

Group: 2

Verdict:

input
100
1000
-1000000000 950042028
-946551105 -1000000000
-940508390 -1000000000
...
view save

correct output
NO
YES
YES
YES
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 17

Group: 2

Verdict:

input
100
1000
-949977239 -1000000000
-948279892 -1000000000
-947497811 -999999999
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 18

Group: 2

Verdict:

input
100
806
-899 -1000
-898 -1000
-896 -999
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 19

Group: 2

Verdict:

input
100
777
-1000 914
-1000 915
-999 916
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 20

Group: 2

Verdict:

input
100
775
-999 998
-995 -1000
-994 -1000
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 21

Group: 2

Verdict:

input
13
2
0 0
1 1
5
...
view save

correct output
YES
YES
NO
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 22

Group: 2

Verdict:

input
1
999748
-995394098 -1000000000
-995392159 -1000000000
-995386584 -999999999
...
view save

correct output
NO
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 23

Group: 2

Verdict:

input
1
1000000
-954368893 -1000000000
-954366895 -1000000000
-954364896 -999999999
...
view save

correct output
YES
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 24

Group: 2

Verdict:

input
1
1000000
-1000000000 928772368
-1000000000 928772506
-999999999 928772642
...
view save

correct output
YES
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 25

Group: 2

Verdict:

input
1
999754
-901705699 -1000000000
-901702695 -1000000000
-901702062 -999999999
...
view save

correct output
NO
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 26

Group: 2

Verdict:

input
100
10000
-1000000000 919783772
-918885599 -1000000000
-918825263 -1000000000
...
view save

correct output
NO
YES
YES
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 27

Group: 2

Verdict:

input
10
99998
-997024120 -77018772
-997011201 -77017738
-996986132 -77015834
...
view save

correct output
YES
YES
NO
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 28

Group: 2

Verdict:

input
100
7934
-10000 9905
-10000 9906
-9999 9906
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 29

Group: 2

Verdict:

input
100
9710
-99754 -6983
-99786 -6055
-99751 -6548
...
view save

correct output
YES
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 30

Group: 2

Verdict:

input
100
2
802396401 -641287652
30956766 -527704723
2
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 31

Group: 2

Verdict:

input
100
3
755025461 -953536159
-402145543 137775005
-700733185 821755784
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 32

Group: 2

Verdict:

input
100
4
-673213071 571383249
-963633735 -859013318
-591788323 791136643
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 33

Group: 2

Verdict:

input
100
5
-124483012 623794901
233757283 -234519096
-987338502 737259422
...
view save

correct output
NO
NO
YES
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 34

Group: 2

Verdict:

input
100
1000
154383911 872030445
-9594726 190227899
908758769 -9615631
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Test 35

Group: 2

Verdict:

input
100
10000
642800667 -694556052
-343795089 -341227394
800920828 676674460
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
Truncated

Tasks

A Sum-B Bit string-C Sunset-D Binary tree-E Function-F Robot-G Classifier-

Submissions (ruhanhabib39)

4:26:36 04:23:04 04:20:50 02:22:31 02:14:03 02:11:30 02:07:14 0