bzoj 4880: [Lydsy1705月赛]排名的战争

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4880

把一个手机看为一个向量
下文称tangjz公司为目标
$(w_1,w_2)$也看作一个向量
那么谁大谁小取决于投影大小，我们设这个向量的斜率为$k$
容易发现，对于在我们目标状态下，左下和右上的点是没有用的。。
要么一直大，要么一直小，判一判丢掉就好了
对于有x，y一样的稍微判一下
剩下右下和左上的
容易发现，存在一个分界点，使得$[k,inf)$是目标优，$[0,k]$是目标差，或者反过来
讨论一下就好了
注意取k这个值，可以当优也可以当差
对于最大最小值的时候，排序顺序有不同，要注意
然后你就可以知道，每一个别的手机对目标贡献排名的范围
排序然后扫一次，记录最大/最小值就好了
然后就没什么了
复杂度是优秀的O(n)

感觉这个模型还挺重要的。。不要忘了

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=100005;
int x[N],y[N];
int n;
struct qq
{
    double k;int c;
}a[N];int nn;
int tot=0,tot1=0;//有多少个在他上面 有多少个在他下面 
int lalal=0;//有多少个
bool cmp (qq x,qq y)	{
    return x.k==y.k?x.c<y.c:x.k>y.k;}
bool cmp1 (qq x,qq y)	{
    return x.k==y.k?x.c>y.c:x.k>y.k;}
int main()
{
    scanf("%d",&n);for (int u=1;u<=n;u++) scanf("%d%d",&x[u],&y[u]);for (int u=2;u<=n;u++){
    bool tf=false;if (x[u]>x[1]&&y[u]>y[1]) tot++,tf=true;if (x[u]<x[1]&&y[u]<y[1]) tf=true;if (x[u]==x[1]&&y[u]==y[1]) tot1++,tf=true;if (tf) continue;double k;if (x[u]==x[1]) {
    k=0;nn++;if (y[u]<y[1])	{
    a[nn].k=k;a[nn].c=1;}else	{
    a[nn].k=k;a[nn].c=-1;lalal++;}}else if (y[u]==y[1]){
    k=1e9;nn++;if (x[u]<x[1])	{
    a[nn].k=k;a[nn].c=-1;lalal++;}else {
    a[nn].k=k;a[nn].c=1;}}else 	{
    k=(double)(y[u]-y[1])/(x[u]-x[1]);k=-1/k;nn++;if (x[u]>x[1]) {
    a[nn].k=k;a[nn].c=1;}else{
    a[nn].k=k;a[nn].c=-1;lalal++;}}}int ans=0;int now=lalal;ans=now;sort(a+1,a+1+nn,cmp);for (int u=1;u<=nn;u++)	{
    now=now+a[u].c;ans=min(ans,now);}printf("%d ",ans+tot+1);now=lalal;ans=now;sort(a+1,a+1+nn,cmp1);for (int u=1;u<=nn;u++)	{
    now=now+a[u].c;ans=max(ans,now);}printf("%d ",ans+tot+1+tot1);return 0;
}