CodeForces/390A

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
Inna and Alarm Clock	★☆☆☆☆	答案正确	100	2015-02-26 13:38:29	无

• 来自寒假练习：2015 Winter Day 3 div1 A题
• 原题链接：http://codeforces.com/problemset/problem/390/A

题意

平面上n个点，最少用几条平行或垂直于x轴的直线才可以全部覆盖。（注意：要求全部同向，第一次交没看到- -）

题解

• 每次选取能覆盖最多的点的直线就好惹。

代码

390A.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<iostream> #include<string> #include<vector> #include<iomanip> #include<algorithm> #include<cstring> #include<cmath> #include<bitset> #include<set> #include<sstream> #include<utility> using namespace std; //数据类型// #define llu unsigned long long #define lld long long //定义默认类型// typedef lld num; #define dsi(n) num n;scanf("%lld",&n) #define si(n) scanf("%lld",&n) //其它// #define reset(x) memset(x,0,sizeof(x)) #define ci const num& #define sqr(x) ((x)*(x)) #define f(i,n) for(num i=1;i<=n;++i) #define ff(i,r,n) for(num i=r;i<=n;++i) #define fi(n) f(i,n) #define f0(i,n) for(num i=0;i!=n;++i) #define fd(i,n) for(num i=n;i>=1;--i) #define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i) #define rforeach(i,s) for(typeof(s.rbegin()) i=s.rbegin();i!=s.rend();++i) #define iforeach(i,s) int idx=0;for(typeof(s.begin()) i=s.begin();i!=s.end();++i,++idx) #define Vector2 pair<num,num> #define vector2(x,y) make_pair(x,y) #define x first #define y second num a1[101][101]={},pointNum1=0,a2[101][101]={},pointNum2=0, xPNum[101]={},yPNum[101]={},xANum[101]={},yANum[101]={}, xP[101][30010]={},yP[101][30010]={}; void init() { reset(xPNum); reset(yPNum); reset(xANum); reset(yANum); f0(i,101)f0(j,101) { if(!a2[i][j])continue; xP[i][++xPNum[i]]=j; yP[j][++yPNum[j]]=i; xANum[i]+=a2[i][j]; yANum[j]+=a2[i][j]; } } num getX() { num c=0; while(1) { ++c; Vector2 ans=vector2(0,0); f0(i,101) ans=max(ans,vector2(xPNum[i],i)); num tx=ans.y; fi(xPNum[tx]) { num ty=xP[tx][i]; yPNum[ty]--; yANum[ty]-=a1[tx][ty]; a1[tx][ty]=0; } pointNum1-=xANum[tx]; xPNum[tx]=xANum[tx]=0; if(!pointNum1) { return c; } } } num getY() { num c=0; while(1) { ++c; Vector2 ans=vector2(0,0); f0(i,101) ans=max(ans,vector2(yPNum[i],i)); num ty=ans.y; fi(xPNum[ty]) { num tx=yP[ty][i]; xPNum[tx]--; xANum[tx]-=a2[tx][ty]; a2[tx][ty]=0; } pointNum2-=yANum[ty]; yPNum[ty]=yANum[ty]=0; if(!pointNum2) { return c; } } } int main() { dsi(n); fi(n) { dsi(x);dsi(y); ++a1[x][y]; ++a2[x][y]; ++pointNum1; ++pointNum2; } init(); num ans1=getX(); init(); num ans2=getY(); cout<<min(ans1,ans2); return 0; }