Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## 根本不需要double好吧~ wa的原因在于二分的时候没有设置line[0]或者 line[n]

Posted by yfsyfs2 at 2020-06-12 15:43:57 on Problem 2318
```16ms 代码如下

//#include "stdafx.h"
//#define LOCAL
#pragma GCC optimize(2)
#pragma G++ optimize(2)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <string>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <map>
//#include <unordered_map>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
#include <stdlib.h>
using namespace std;
//#define int unsigned long long
//#define int long long
#define re register int
#define ci const int
typedef pair<int, int> P;
#define FE(cur) for(re h = head[cur], to, len; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define ild inline double
#define ilp inline P
#define LEN(cur) (hjt[cur].r - hjt[cur].l)
#define MID(cur) (hjt[cur].l + hjt[cur].r >> 1)
typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;
typedef map<int, int>::iterator mit;
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), *pr2 = 0, pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
ili read(int &x)
{
x = 0; int f = 1; char c = gc(); if (!~c) return EOF;
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f; return 1;
}
ili read(double &x)
{
int xx = 0; double f = 1.0, fraction = 1.0; char c = gc(); if (!~c) return EOF;
while (!isdigit(c)) { if (c == '-') f = -1.0; c = gc(); }
while (isdigit(c)) { xx = (xx << 3) + (xx << 1) + (c ^ 48), c = gc(); }
x = xx;
if (c ^ '.') { x = f * xx; return 1; }
c = gc();
while (isdigit(c)) x += (c ^ 48) * (fraction /= 10), c = gc();
x *= f; return 1;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
ili read(char *x)
{
char c = gc(); if (!~c) return EOF;
while(!isalpha(c) && !isdigit(c)) c = gc();
while (isalpha(c) || isdigit(c)) *x++ = c, c = gc();
*x = 0; return 1;
}
ili readln(char *x)
{
char c = gc(); if (!~c) return EOF;
while(c == 10) c = gc();
while(c >= 32 && c <= 126) *x++ = c, c = gc();
*x = 0; return 1;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
ilv write(char c) { pc(c); }
ilv writeln(char c) { write(c); pc(10); }
} using namespace fastio;
#define cp const Point
const int maxn = 5005;
int n, m, x1, y_1, x2, y2, u[maxn], l[maxn], ans[maxn];
struct Point
{
int x, y;
Point(){}
Point(int x, int y):x(x), y(y){}
int operator / (cp &o) const
{
return x * o.y - y * o.x;
}
};

ili ck(int i, int x, int y)
{
return Point(x - u[i], y - y_1) / Point(l[i] - u[i], y2 - y_1) < 0;
}

ili kk(int x, int y)
{
int lo = 0, hi = n, mid, ans = 0;
while (lo <= hi)
{
mid = lo + hi >> 1;
if (ck(mid, x, y)) // 如果 (x, y) 在 直线 mid 的右侧
{
ans = mid;
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return ans;
}

signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
freopen("d:\\my.out", "w", stdout);
#endif
int flag = 1;
while (read(n), n)
{
if (!flag) writeln("");
if (flag) flag = 0;
memset(ans, 0, sizeof(ans));
read(m), read(x1), read(y_1), read(x2), read(y2);
u[0] = l[0] = x1;
for (re i = 1; i <= n; i++)
{
read(u[i]), read(l[i]);
}
int x, y;
while (m--)
{
read(x), read(y);
++ans[kk(x, y)];
}
for (re i = 0; i <= n; i++) write(i), write(": "), writeln(ans[i]);
}
flush();
return 0;
}```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator