gdutcode Stubirdと彼の女性ファン
3385 ワード
http://gdutcode.sinaapp.com/problem.php?cid=1025&pid=3
Stubirdと彼の女性ファン
Description
合宿チームは勉強の雰囲気がいいだけでなく、みんなと仲良く過ごしています.x 1、doubleegg、wingkouとStubirdは、シャベルを打ちながらトランプをしています.次の日に女性ファンに会いたいと思っています.この日はn人の女性ファンが彼を訪ねてきました.明日の朝はどこで彼を待っているかを教えてくれました.プレゼントを準備しましたが、ファンが多すぎて、Stubirdはファン全員に会うことができません.だから彼は翌日に一番多くの女性ファンに会える道を行くつもりです.地図を二次元平面として見ることができます.Stubirdはホテルの入り口から出発します.座標はsx、syです.彼は方向を選んで、その方向に沿ってまっすぐ行くしかないです.Stubirdが女性ファンに会った時に彼女のプレゼントをもらうことができます.そこで、Stubirdはこの事のため、一晩考えました.だから彼もカードを洗って一晩中洗濯しました.もちろん服喪しないです.だから彼は社会に報復して、この問題をあなたを試験するつもりです.
Input
最初の行にサンプル数Tを入力します.
次の行はn、sx、sy、代表n(1<=n==15000万)の女性ファン、Stubirdの位置sx、syです.
次のn行の座標は、女性ファンの座標を表します.座標は0-1000の整数です.
Output
出力Stubirdは最大何人の女性ファンに会えますか?
Sample Input
12 1 12 23
Sample Output
2
一方の方向にしか歩けないので、傾きを判断してはいけません.傾きが等しい場合は、2つの反対の方向にあるかもしれません.(x 1-x 2)、(y 1-y 2)を考慮して、(x 1-x 2)、(y 1-y 2)の最大公約数を除いて、並べ替え処理して、(x 1-x 2)、(y 1-y 2)を0とする場合の特殊処理は、具体的にコードを見てください.
Stubirdと彼の女性ファン
Description
合宿チームは勉強の雰囲気がいいだけでなく、みんなと仲良く過ごしています.x 1、doubleegg、wingkouとStubirdは、シャベルを打ちながらトランプをしています.次の日に女性ファンに会いたいと思っています.この日はn人の女性ファンが彼を訪ねてきました.明日の朝はどこで彼を待っているかを教えてくれました.プレゼントを準備しましたが、ファンが多すぎて、Stubirdはファン全員に会うことができません.だから彼は翌日に一番多くの女性ファンに会える道を行くつもりです.地図を二次元平面として見ることができます.Stubirdはホテルの入り口から出発します.座標はsx、syです.彼は方向を選んで、その方向に沿ってまっすぐ行くしかないです.Stubirdが女性ファンに会った時に彼女のプレゼントをもらうことができます.そこで、Stubirdはこの事のため、一晩考えました.だから彼もカードを洗って一晩中洗濯しました.もちろん服喪しないです.だから彼は社会に報復して、この問題をあなたを試験するつもりです.
Input
最初の行にサンプル数Tを入力します.
次の行はn、sx、sy、代表n(1<=n==15000万)の女性ファン、Stubirdの位置sx、syです.
次のn行の座標は、女性ファンの座標を表します.座標は0-1000の整数です.
Output
出力Stubirdは最大何人の女性ファンに会えますか?
Sample Input
12 1 12 23
Sample Output
2
一方の方向にしか歩けないので、傾きを判断してはいけません.傾きが等しい場合は、2つの反対の方向にあるかもしれません.(x 1-x 2)、(y 1-y 2)を考慮して、(x 1-x 2)、(y 1-y 2)の最大公約数を除いて、並べ替え処理して、(x 1-x 2)、(y 1-y 2)を0とする場合の特殊処理は、具体的にコードを見てください.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <queue>
#include <stack>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
#define N 4151000
#define INF 0x3f3f3f3f
#define PI acos (-1.0)
#define EPS 1e-5
#define met(a, b) memset (a, b, sizeof (a))
struct node
{
int x, y;
}p[N];
bool cmp (node a, node b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int gcd (int a, int b)
{
if (a % b == 0) return b;
return gcd (b, a%b);
}
int main ()
{
int t;
scanf ("%d", &t);
while (t--)
{
int n, sx, sy, x, y;
scanf ("%d %d %d", &n, &sx, &sy);
for (int i=0; i<n; i++)
{
scanf ("%d %d", &x, &y);
p[i].x = x - sx, p[i].y = y - sy;
if (p[i].y)
{///
int k = gcd (abs (p[i].x), abs (p[i].y));
p[i].x /= k, p[i].y /= k;
}
}
sort (p, p+n, cmp);
int maxn = 0, cnt = 1, cnt1 = 0, cnt2 = 0, ans = 0;
if (!p[0].x && !p[0].y) ans++;
for (int i=0; i<n; i++)
{/// (y1-y2) 0 ,s ,
if (!p[i].y && p[i].x < 0) cnt1++;
if (!p[i].y && p[i].x > 0) cnt2++;
}
maxn = max (maxn, max (cnt1, cnt2));
cnt1 = 0, cnt2 = 0;
for (int i=0; i<n; i++)
{/// (x1-x2) 0 ,s ,
if (!p[i].x && p[i].y < 0) cnt1++;
if (!p[i].x && p[i].y > 0) cnt2++;
}
maxn = max (maxn, max (cnt1, cnt2));
for (int i=1; i<n; i++)
{
if (!p[i].x && !p[i].y)
{/// S ,
ans++;
continue;
}
if ((p[i].x == p[i-1].x && p[i].y == p[i-1].y))
cnt++;
else
{
maxn = max (maxn, cnt);
cnt = 1;
}
}
maxn = max (maxn, cnt);
if (ans == n) ans--;
printf ("%d
", ans+maxn);
}
return 0;
}