做法~
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (1000)
int main()
{
long long ans=0;
for (int i=1;i<1000;i++)
if (!(i%3&&i%5)) ans+=i;
cout< <333*3+5*199<
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (1000)
int main()
{
long long ans=0;
for (int i=1;i<1000;i++)
if (!(i%3&&i%5)) ans+=i;
cout< <333*3+5*199<
A Funny Game
Description
Alice and Bob decide to play a funny game. At the beginning of the game they pick n(1 <= n <= 106) coins in a circle, as Figure 1 shows. A move consists in removing one or two adjacent coins, leaving all other coins untouched. At least one coin must
be removed. Players alternate moves with Alice starting. The player that removes the last coin wins. (The last player to move wins. If you can't move, you lose.) Note: For n > 3, we use c1, c2, ..., cn to denote the coins clockwise and if Alice remove c2, then c1 and c3 are NOT adjacent! (Because there is an empty place between c1 and c3.) Suppose that both Alice and Bob do their best in the game. Input
There are several test cases. Each test case has only one line, which contains a positive integer n (1 <= n <= 106). There are no blank lines between cases. A line with a single 0 terminates the input.
Output
For each test case, if Alice win the game,output "Alice", otherwise output "Bob".
Sample Input 1 2 3 0 Sample Output Alice Alice Bob Source
POJ Contest,Author:Mathematica@ZSU
|
博弈第一招——对称博弈。
思路:无论对方怎么取,我都取与它对称(或者相反/一样的)
#include<cstdio> #include<cstdlib> #include<algorithm> #include<functional> #include<cstring> #include<iostream> using namespace std; int main() { int n; while(scanf("%d",&n)&&n) { if (n>=3) cout<<"Bob"<<endl; else cout<<"Alice"<<endl; } return 0; }
Language:
Square
Description
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
Input
The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.
Output
For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".
Sample Input 3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5 Sample Output yes no yes Source |
《搜索是怎样剪枝的-1》
1.只要找到3条边。
2.从大到小顺序找。
3.每次搜边时要确定边的相对顺序唯一(直接从TLE→秒)
#include<cstdio> #include<cstdlib> #include<algorithm> #include<functional> #include<cstring> #include<iostream> using namespace std; #define MAXM (20+10) int tt,n,a[MAXM],cnt,len; bool b[MAXM],flag; bool dfs(int l,int x,int pre) { // cout<<l<<' '<<x<<' '<<kth<<endl; if (x==len) {l++;x=0;pre=n-1;} if (l==4) { return 1; } for(int i=pre-1;i;i--) if (!b[i]&&x+a[i]<=len) { b[i]=1; if (dfs(l,x+a[i],i)) return 1; b[i]=0; // if (!x) return 0; } return 0; } int main() { scanf("%d",&tt); while (tt--) { cnt=0; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); cnt+=a[i];b[i]=0; } sort(a+1,a+1+n); if (n<4||cnt%4||a[n]>cnt/4) { printf("non");continue; } b[n]=1;len=cnt/4; if (dfs(1,a[n],n)) { printf("yesn"); } else printf("non"); } return 0; }
Language:
The Bottom of a Graph
Description
We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges.
Then G=(V,E) is called a directed graph. Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1). Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e.,bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs. Input
The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer
numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with the meaning that (vi,wi)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero. Output
For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.
Sample Input 3 3 1 3 2 3 3 1 2 1 1 2 0 Sample Output 1 3 2 Source |
Tarjen缩点统计出度。
#include<cstdio> #include<cstdlib> #include<algorithm> #include<functional> #include<cstring> #include<iostream> using namespace std; #define MAXN (5000+10) #define MAXM (1000000+10) int n,m,h[MAXN],t[MAXN],dfs[MAXN],tim,kind,s[MAXN],tot; bool b[MAXN]; int edge[MAXM],next[MAXM],pre[MAXN],size; int x[MAXM],y[MAXM],numk[MAXN]; void addedge(int u,int v) { edge[++size]=v; next[size]=pre[u]; pre[u]=size; } void tar(int u) { dfs[u]=t[u]=++tim;b[u]=1;s[++tot]=u; for (int p=pre[u];p;p=next[p]) { int &v=edge[p]; if (!b[v]) tar(v),dfs[u]=min(dfs[u],dfs[v]); else if (!h[v]) dfs[u]=min(dfs[u],t[v]); //保证指向祖先 } if (dfs[u]==t[u]) { kind++; while (s[tot]!=u) h[s[tot--]]=kind,numk[kind]++; h[s[tot--]]=kind;numk[kind]++; } } int outdegree[MAXN]; int main() { while (scanf("%d",&n)&&n) { scanf("%d",&m); tot=size=tim=kind=0; memset(h,0,sizeof(h)); memset(t,0,sizeof(t)); memset(dfs,0,sizeof(dfs)); memset(s,0,sizeof(s)); memset(pre,0,sizeof(pre)); memset(b,0,sizeof(b)); memset(numk,0,sizeof(numk)); memset(outdegree,0,sizeof(outdegree)); for (int i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); addedge(x[i],y[i]); } for (int i=1;i<=n;i++) if (!b[i]) tar(i); // for (int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl; for (int i=1;i<=m;i++) { if (h[x[i]]^h[y[i]]) outdegree[h[x[i]]]++; } /* int ans=0; for (int i=1;i<=kind;i++) if (!outdegree[i]) ans+=numk[i]; cout<<ans<<endl; */ bool flag=0; for (int i=1;i<=n;i++) if (!outdegree[h[i]]) { if (flag) printf(" ");else flag=1;printf("%d",i); } // cout<<ans<<endl; cout<<endl; } return 0; }
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 186 Solved: 104
[Submit][Status][Discuss]
沫沫最近在玩一个二维的射箭游戏,如下图 1 所示,这个游戏中的 x 轴在地面,第一象限中有一些竖直线段作为靶子,任意两个靶子都没有公共部分,也不会接触坐标轴。沫沫控制一个位于(0,0)的弓箭手,可以朝 0 至 90?中的任意角度(不包括 0度和 90度),以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力,并且光之箭没有箭身,箭的轨迹会是一条标准的抛物线,被轨迹穿过的所有靶子都认为被沫沫射中了,包括那些 只有端点被射中的靶子。这个游戏有多种模式,其中沫沫最喜欢的是闯关模式。在闯关模式中,第一关只有一个靶
子,射中这个靶子即可进入第二关,这时在第一关的基础上会出现另外一个靶子,若能够一箭 双雕射中这两个靶子便可进入第三关,这时会出现第三个靶子。依此类推,每过一关都会新出 现一个靶子,在第 K 关必须一箭射中前 K 关出现的所有 K 个靶子才能进入第 K+1 关,否则游戏 结束。沫沫花了很多时间在这个游戏上,却最多只能玩到第七关“七星连珠”,这让她非常困惑。 于是她设法获得了每一关出现的靶子的位置,想让你告诉她,最多能通过多少关
输入文件第一行是一个正整数N,表示一共有N关。接下来有N行,第i+1行是用空格隔开的三个正整数xi,yi1,yi2(yi1<yi2 ),表示第i关出现的靶子的横坐标是xi,纵坐标的范围是从yi1到yi2 。
输入保证30%的数据满足N≤100,50%的数据满足N≤5000,100%的数据满足N≤100000且给 出的所有坐标不超过109 。
仅包含一个整数,表示最多的通关数。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<functional> #define MAXN (100000+10) #define MAXCi (1000000000) #define eps 1e-15 #define For(i,n) for(int i=1;i<=n;i++) using namespace std; int n; struct P { double x,y; P(){} P(double _x,double _y):x(_x),y(_y){} }p[MAXN*4]; struct V { double x,y; V(){} V(double _x,double _y):x(_x),y(_y){} V(P a,P b):x(b.x-a.x),y(b.y-a.y){} friend double operator*(V a,V b){return a.x*b.y-a.y*b.x;} friend V operator*(double a,V b){return V(a*b.x,a*b.y);} friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);} }; struct line { P p; V v; double ang; int i; line(){} line(double _x,double _y,double _a,double _b,int _i):p(P(_x,_y)),v(V(_a,_b)),i(_i){ang=atan2(v.y,v.x);} bool onleft(P A) { return v*V(p,A)>=0; } bool operator<(const line& l) const { return ang<l.ang; } friend P getinter(line a,line b) { /* V u=V(a.p,b.p); double t=(a.v*u)/(b.v*a.v); return b.p+(t*b.v); double s1=V(a.p,b.p+b.v)*a.v; double s2=a.v*V(a.p,b.p); return b.p+(-s1/(s1+s2))*b.v; // V u=V(a.p,b.p); */ V u=V(b.p,a.p); double t=(b.v*u)/(a.v*b.v); return a.p+t*a.v; } }que[MAXN*10],q[MAXN*4]; int size=0; int half_intersection(line *l,int n) { int first=1,last=0; for (int i=1;i<=size;i++) { if (l[i].i>n) continue; if (!last) {q[++last]=l[i];continue;} while (first<last&&!l[i].onleft(p[last-1])) last--; while (first<last&&!l[i].onleft(p[first])) first++; if (fabs(q[last].v*l[i].v)<=eps) { if (q[last].onleft(l[i].p)) q[last]=l[i]; } else q[++last]=l[i]; if (first<last) p[last-1]=getinter(q[last-1],q[last]); } bool flag=1; while (flag) { flag=0; while (first<last&&!q[first].onleft(p[last-1])) last--,flag=1; while (first<last&&!q[last].onleft(p[first])) first++,flag=1; } /* p[last]=getinter(q[last],q[first]); for (int i=first;i<=last;i++) printf("%lf %lfn",p[i].x,p[i].y); cout<<endl; */ return last-first>1; } void pri(line a,line b) { P c=getinter(a,b); printf("%.lf %.lfn",c.x,c.y); } int main() { freopen("archery.in","r",stdin); freopen("archery.out","w",stdout); cin>>n; que[1]=line(0,0,0,1,0); que[2]=line(-1,0,1,0,0); que[3]=line(0,MAXCi,-1,0,0); que[4]=line(-MAXCi,MAXCi,0,-1,0);size=4; // pri(que[3],que[4]); // size=0; for (int i=1;i<=n;i++) { double x,l,r; scanf("%lf%lf%lf",&x,&l,&r); que[++size]=line(0,l/x,1/x,-1,i); que[++size]=line(0,r/x,-1/x,1,i); } sort(que+1,que+1+size); // cout<<size<<endl; // for (int i=l;i<=r;i++) cout<<halsf_intersection(que,i)<<' '; // cout<<half_intersection(que,50001); int l=0,r=n,Mid=0; while (l<=r) { int mid=(l+r)>>1; if (half_intersection(que,mid)) {Mid=mid;l=mid+1;}else r=mid-1; } cout<<Mid<<endl; return 0; }
打地鼠是这样的一个游戏:地面上有一些地鼠洞,地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时,用锤子砸其头部,砸到的地鼠越多分数也就越高。
游戏中的锤子每次只能打一只地鼠,如果多只地鼠同时探出头,玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了,所以你改装了锤子,增加了锤子与地面的接触面积,使其每次可以击打一片区域。如果我们把地面看做M*N的方阵,其每个元素都代表一个地鼠洞,那么锤子可以覆盖R*C区域内的所有地鼠洞。但是改装后的锤子有一个缺点:每次挥舞锤子时,对于这R*C的区域中的所有地洞,锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中,每个地洞必须至少有1只地鼠,且如果某个地洞中地鼠的个数大于1,那么这个地洞只会有1只地鼠被打掉,因此每次挥舞锤子时,恰好有R*C只地鼠被打掉。由于锤子的内部结构过于精密,因此在游戏过程中你不能旋转锤子(即不能互换R和C)。
你可以任意更改锤子的规格(即你可以任意规定R和C的大小),但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后,再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠,至少需要挥舞锤子的次数。
Hint:由于你可以把锤子的大小设置为1*1,因此本题总是有解的。
第一行包含两个正整数M和N;
下面M行每行N个正整数描述地图,每个数字表示相应位置的地洞中地鼠的数量。
输出一个整数,表示最少的挥舞次数。
二分判断+贪心
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #define MAXN (100+10) #define INF (1000000000) #define For(i,n) for(int i=1;i<=n;i++) using namespace std; int n,m,a[MAXN][MAXN],a2[MAXN][MAXN]; int is_ok(int l,int r) { memcpy(a2,a,sizeof(a)); int sum=0; For(i,n-l+1) For(j,m-r+1) if(a2[i][j]) { int delta=a2[i][j];sum+=delta; for (int k=i;k<=i+l-1;k++) for (int k2=j;k2<=j+r-1;k2++) if (a2[k][k2]<delta) return 0; else a2[k][k2]-=delta; } return sum; } int main() { scanf("%d%d",&n,&m); int cnt=0,ans=0; For(i,n) For(j,m) {scanf("%d",&a[i][j]);cnt+=a[i][j];} For(i,n) For(j,m) { if (i*j<ans) continue; if (!(cnt%(i*j))&&is_ok(i,j)*i*j==cnt) { ans=i*j; } } cout<<cnt/ans<<endl; return 0; }
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 375 Solved: 239
[Submit][Status][Discuss]
【数据范围】
对于60%的数据,0<N<=2^16。
对于100%的数据,0<N<=2^32。
欧拉函数:
枚举n的约数k,令s(k)为满足gcd(m,n)=k,(1<=m<=n) m的个数,则ans=sigma(k*s(k)) (k为n的约数)
因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)
枚举n的约数即可,复杂度o(sqrt(n))
PS:刚刚ksy告诉我C++,直接读int比读char转int慢(——0)
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<functional> #include<algorithm> #include<cctype> #include<iostream> using namespace std; #define MAXN (2<<31) long long ans=0,n; long long phi(long long n) { if (n==1) return 1; // cout<<n; long long ans=1; for (long long i=2;i*i<=n;i++) if (n%i==0) { int k=0; while (n%i==0) {k++,n/=i;} ans*=i-1; for (int j=2;j<=k;j++) ans*=i; } if (n>1) ans*=n-1; // cout<<' '<<ans<<endl; return ans; } int main() { cin>>n; for (int i=1;i*i<=n;i++) if (n%i==0) { ans+=(long long)i*phi(n/i); if (i*i<n) ans+=(long long)n/i*phi(i); } cout<<ans<<endl; return 0; }
INeedYou IMissYou ILoveYou
4 15
这题是统计公共子序列个数+去重
正解用了容斥原理,并且允许空串。
F[I][J][K]=2F[I-1][J-1][K-1]-F[I'-1][J'-1][K'-1] I',J',K'为I,J,K,之前出现a[i],b[j],c[k]的位置(没有就不用减)
假设之前已经去重,那么F[I][J][K]只需与F[I'-1][J'-1][K'-1]去重。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<functional> #include<algorithm> #include<cctype> using namespace std; #define F (2769433) #define MAXN (100+10) #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<=n;i++) int len1,len2,len3,f[MAXN][MAXN][MAXN],pre1[MAXN],pre2[MAXN],pre3[MAXN],s[500]; char a[MAXN],b[MAXN],c[MAXN]; void make_pre(char *a,int n,int *pre) { memset(s,128,sizeof(s)); memset(pre,0,sizeof(pre)); For(i,n) { a[i]=tolower(a[i]); pre[i]=s[a[i]]; s[a[i]]=i; } } int main() { memset(f,0,sizeof(f)); scanf("%s%s%s",a+1,b+1,c+1);a[0]=b[0]=c[0]=' '; len1=strlen(a)-1,len2=strlen(b)-1,len3=strlen(c)-1; make_pre(a,len1,pre1); make_pre(b,len2,pre2); make_pre(c,len3,pre3); int cnt=0; For(i,len1) For(j,len2) For(k,len3) if (a[i]==b[j]&&b[j]==c[k]) f[i][j][k]=f[i-1][j-1][k-1]+1; else f[i][j][k]=max(max(f[i-1][j][k],f[i][j-1][k]),f[i][j][k-1]); cnt=f[len1][len2][len3]; // memset(f,0,sizeof(f)); Rep(i,len1) Rep(j,len2) Rep(k,len3) f[i][j][k]=1; For(i,len1) For(j,len2) For(k,len3) { f[i][j][k]=0; if (a[i]==b[j]&&b[j]==c[k]) { f[i][j][k]=(10*F+f[i-1][j-1][k-1]*2)%F; if (pre1[i]>0&&pre2[j]>0&&pre3[k]>0) f[i][j][k]=(F+f[i][j][k]-f[pre1[i]-1][pre2[j]-1][pre3[k]-1])%F; // if (!pre1[i]||!pre2[j]||!pre3[k]) f[i][j][k]--; } else { f[i][j][k]=(10*F+f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i-1][j-1][k]-f[i][j-1][k-1]-f[i-1][j][k-1]+f[i-1][j-1][k-1])%F; } } printf("%dn%dn",cnt,(F+f[len1][len2][len3]-1)%F); return 0; }
Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge
Submit: 258 Solved: 137
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #include<cmath> using namespace std; #define MAXN (50000+10) #define INF (1000000000) #define eps 1e-6 struct P { double x,y; P(){} P(double _x,double _y):x(_x),y(_y){} friend bool operator<(P a,P b){return (fabs(a.y-b.y)<eps)?a.x<b.x:a.y<b.y; } friend bool operator==(P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;} friend bool operator!=(P a,P b){return !(a==b);} }a[MAXN],s[MAXN],ansp[5]; int size=0; double ans=INF; double dis2(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);} struct V { double x,y; V(){} V(double _x,double _y):x(_x),y(_y){} V(P a,P b):x(b.x-a.x),y(b.y-a.y){} friend double operator*(V a,V b){return a.x*b.y-a.y*b.x;} friend V operator*(double a,V b){return V(a*b.x,a*b.y);} friend double operator/(V a,V b){return a.x*b.x+a.y*b.y;} friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);} friend P operator-(P a,V b){return P(a.x-b.x,a.y-b.y);} friend V operator~(V a){return V(a.y,-a.x);} double dis2(){return x*x+y*y; } }c[MAXN]; int cmp(P A,P B) { double tmp=V(a[1],A)*V(a[1],B); if (tmp>0) return 1; else if (fabs(tmp)<eps) return (-dis2(A,a[1])-dis2(B,a[1])>0); return 0; } int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); for (int i=2;i<=n;i++) if (a[i]<a[1]) swap(a[1],a[i]); sort(a+2,a+1+n,cmp); s[1]=a[1];size=1; for (int i=2;i<=n;) if (size<2||V(s[size-1],s[size])*V(s[size],a[i])>eps) s[++size]=a[i++]; else size--; s[0]=s[size]; int l=1,r=1,t=1; for (int i=0;i<size;i++) { while (V(s[i],s[i+1])*V(s[i],s[t+1])-V(s[i],s[i+1])*V(s[i],s[t])>-eps) t=(t+1)%size; while (V(s[i],s[i+1])/V(s[i],s[r+1])-V(s[i],s[i+1])/V(s[i],s[r])>-eps) r=(r+1)%size; if (i==0) l=r; while (V(s[i],s[i+1])/V(s[i],s[l+1])-V(s[i],s[i+1])/V(s[i],s[l])<eps) l=(l+1)%size; double Dis2=dis2(s[i],s[i+1]),wlxdis=V(s[i],s[i+1])/V(s[i],s[l]),wrxdis=V(s[i],s[i+1])/V(s[i],s[r]),hxdis=V(s[i],s[i+1])*V(s[i],s[t]); double tmp=hxdis*(wrxdis-wlxdis)/Dis2; if (tmp<0) tmp=-tmp; if (ans>tmp) { ans=tmp; ansp[0]=s[i]-(wlxdis/Dis2)*V(s[i+1],s[i]); ansp[1]=s[i]+(wrxdis/Dis2)*V(s[i],s[i+1]); ansp[2]=ansp[1]+(hxdis/Dis2)*(~V(s[i+1],s[i])); ansp[3]=ansp[0]+(hxdis/Dis2)*(~V(s[i+1],s[i])); } } int p=0; for (int i=1;i<4;i++) if (ansp[i]<ansp[p]) p=i;//p=0; printf("%.5lfn",ans); for (int i=0;i<4;i++) printf("%.5lf %.5lfn",ansp[(p+i)%4].x,ansp[(p+i)%4].y); return 0; }
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1830 Solved: 656
[Submit][Status][Discuss]
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<functional> #include<iostream> using namespace std; #define MAXN (50000+10) int n; struct line { int k,b,i; friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k; } friend double intx(line a,line b) { return (double)(b.b-a.b)/(a.k-b.k); } }a[MAXN]; int s[MAXN],size=0; void push(int x) { while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--; s[++size]=x; } bool b[MAXN]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;} sort(a+1,a+1+n); push(1); for (int i=2;i<=n;i++) if (a[i].k>a[i-1].k) push(i); // for (int i=1;) memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1; for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' '; return 0; }