1月上旬题解

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 ll a,b,c,d;
 6 ll mi,mx,x,y;
 7 int main()
 8 {
 9     int n;
10     while (scanf("%lld%lld%lld%lld",&a,&b,&c,&d)!=EOF)
11     {
12         scanf("%d",&n);
13         mi=1e20; mx=0;
14         for (int i=0; i<n; i++)
15         {
16             scanf("%lld%lld",&x,&y);
17             mi=min(mi,a*c*x*x+b*d*y*y+(a*d+b*c)*x*y);
18             mx=max(mx,a*c*x*x+b*d*y*y+(a*d+b*c)*x*y);
19         }
20         printf("%lld\n",(ll)(fabs(1.0*(mx-mi)/(a*d-b*c))+0.5));
21     }
22     return 0;
23 }

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 struct node{int x,y,id;} a[200010];
 5 int b[200010],c[200010],op[200010],wh[200010],f[200010];
 6 int n;
 7 
 8 void add(int x,int w)
 9 {
10     for (int i=x; i<=2*n; i+=i&(-i))
11       b[i]=max(b[i],w);
12 }
13 
14 int ask(int x)
15 {
16     int s=0;
17     for (int i=x; i; i-=i&(-i))
18       s=max(b[i],s);
19     return s;
20 }
21 bool cmp(node a,node b)
22 {
23     if (a.x==b.x&&a.y==b.y) return a.id<b.id;
24     if (a.x==b.x) return a.y<b.y;
25     return a.x<b.x;
26 }
27 
28 int main()
29 {
30   //  freopen("1.in","r",stdin);
31     scanf("%d",&n);
32     while (n)
33     {
34         for (int i=1; i<=n; i++)
35         {
36             scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i+n].x,&a[i+n].y);
37             a[i].id=i;
38             a[i+n].id=i+n;
39             b[i]=a[i].y; b[i+n]=a[i+n].y;
40         }
41         sort(a+1,a+1+2*n,cmp);
42         sort(b+1,b+1+2*n);
43         int m=1; c[1]=b[1];
44         for (int i=2; i<=2*n; i++) if (b[i]!=b[i-1]) c[++m]=b[i];
45         for (int i=1; i<=2*n; i++)
46         {
47             a[i].y=lower_bound(c+1,c+1+m,a[i].y)-c;
48             if (a[i].id<=n) op[a[i].id]=i;
49         }
50         for (int i=1; i<=2*n; i++)
51             if (a[i].id>n) wh[i]=op[a[i].id-n];
52         memset(b,0,sizeof(b));
53         int ans=0;
54         for (int i=1; i<=2*n; i++)
55         {
56             if (a[i].id<=n)
57             {
58                 f[i]=ask(a[i].y-1)+1;
59                 ans=max(ans,f[i]);
60             }
61             else add(a[i].y,f[wh[i]]);
62         }
63         printf("%d\n",ans);
64         scanf("%d",&n);
65     }
66 }