Submission #13969

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
13969	2015-04-24 16:59:05	ainta	Be Two Bees (OJUZ10_b2b)	C++98	100 / 100	55 ms	3844 KiB

b2b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
double Sh;
struct point{
  double x, y;
  int num;
  bool operator<(const point &p)const{
    return x < p.x;
  }
}w[101000];
double ccw(point a, point b, point c){
  return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
int st[101000], m, p1, p2;
double X, Y, Res = 1e20;
double Gap(int t){
  return (Y + w[st[t]].y) / (X + w[st[t]].x);
}
void Do(int num){
  X = w[num].x, Y = Sh + w[num].y;
  int b = 1, e = m - 1, mid, r = 1;
  while (b <= e){
    mid = (b + e) >> 1;
    if (Gap(mid) >= Gap(mid + 1)){
      b = r = mid + 1;
    }
    else e = mid - 1;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 28 / 28
• Subtask 4: 39 / 39